Run ID 作者 问题 语言 测评结果 分数 时间 内存 代码长度 提交时间
33867 LYLAKIOI 【BJ】T2 C++ 运行出错 23 591 MS 85124 KB 2290 2024-10-24 16:30:45

Tests(3/13):


#include<bits/stdc++.h> #define up(i,l,r) for(int i=(l);i<=(r);++i) #define down(i,l,r) for(int i=(l);i>=(r);--i) #define pi pair<int,int> #define p1 first #define p2 second #define p_b push_back #define m_p make_pair using namespace std; typedef long long ll; const int maxn=1e6+10,mod=1e9+7; inline ll read(){ ll x=0;short t=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')t=-1;ch=getchar();} while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar(); return x*t; } inline char gc(){ char ch=getchar(); while(ch!='-'&&ch!='?')ch=getchar(); return ch; } int n,m,res,ndct,bel[maxn],vis[maxn],hd[maxn]; struct Dsu { int fa[maxn]; int fd(int u){ if(u==fa[u])return u; return fa[u]=fd(fa[u]); } void init(int n){ up(i,1,n)fa[i]=i; } }dsu; vector<pi>v[maxn]; map<pi,int>pos; map<pi,int>ID; struct nd { int x,y,bel,del; }d[maxn<<1]; void fc(){ up(i,1,n)up(j,0,int(v[i].size())-1)pos[m_p(i,v[i][j].p1)]=j; for(int i=2;i<=2*m+1;i++)if(!d[i].bel){ d[i].bel=++ndct; int u=d[i].y,lst=d[i].x; int cc=0; while(u!=d[i].x){ int p=pos[m_p(u,lst)]; auto it=((p==v[u].size()-1)?v[u][0]:v[u][p+1]); d[it.p2].bel=ndct; lst=u,u=it.p1; } }dsu.init(ndct); } void slv(){ n=read();int q=read(); up(i,1,n){ int k=read(); while(k--){ int x=read(); if(ID.count(m_p(i,x))){ v[i].p_b(m_p(x,ID[m_p(i,x)])); continue; } ++m; d[m*2].x=i,d[m*2].y=x;ID[m_p(i,x)]=m*2; d[m*2+1].x=x,d[m*2+1].y=i;ID[m_p(x,i)]=m*2+1; v[i].p_b(m_p(x,ID[m_p(i,x)])); } }fc(); int res=1,lst=0; while(q--){ char op=gc();assert(op=='-'); int x=read()^lst,y=read()^lst; int id=ID[m_p(x,y)]; int a=d[id].bel,b=d[id^1].bel; if(dsu.fd(a)==dsu.fd(b))res++; dsu.fa[dsu.fd(a)]=dsu.fd(b); lst=res;printf("%d\n",res); } } int main(){ //freopen("planar.in","r",stdin); //freopen("planar.out","w",stdout); slv(); fclose(stdin); fclose(stdout); return 0; }


测评信息: