提交时间:2024-01-13 19:35:38
运行 ID: 24910
#include <iostream> #include <cstdio> #include <math.h> #include <algorithm> #include <istream> #include <string> #include <queue> #include <deque> #include <random> #include <stack> #include <set> #include <string.h> #include <map> #include <unordered_map> #include <sstream> #include <bitset> #include <fstream> #include <climits> #include <time.h> #include <cassert> using namespace std; #define int long long #define double long double #define endl "\n" #define pii pair<int,int> #define p1(x) ((x).first) #define p2(x) ((x).second) int n,q,m,cnt; map<pii,int>id; map<int,int>nxt[100030],us[100300]; pii e[1000300]; vector<int>g[100300]; int ud[1000030],vd[1000300]; bool ic[100300]; inline void add(int i,int x){ if(ud[i])vd[i]=x; else ud[i]=x; } int f[1000030]; int dfn[1000300]; int low[1000030],tk; int cut[1003000]; inline void dfs(int u,int fid){ dfn[u]=low[u]=++tk; for(int id:g[u])if(id!=fid){ int v=p1(e[id])+p2(e[id])-u; if(!dfn[v]) dfs(v,id),low[u]=min(low[u],low[v]); else low[u]=min(low[u],dfn[v]); } if(low[u]==dfn[u]&&fid) cut[fid]=1; } int res=1; inline int ff(int x){ return f[x]==x?x:f[x]=ff(f[x]); } inline bool merge(int x,int y){ x=ff(x),y=ff(y); if(x==y)return 1; f[x]=y; return 0; } int D[100300]; inline bool del(int id){ if(D[id])return 0; D[id]=1; bool r=0; res+=r=merge(ud[id],vd[id]); return r; } int cb; int bel[100300]; bool ins[100300]; signed main(){ ios::sync_with_stdio(0); cin.tie(0),cout.tie(0); cin>>n>>q; for(int i=1;i<=n;i++){ int k; cin>>k; while(k--){ int x=i,y; cin>>y; if(!id[{x,y}]){ id[{x,y}]=++m; id[{y,x}]=m; e[m]={x,y}; } g[i].push_back(id[{x,y}]); } } //dfs(1,0); for(int u=1;u<=n;u++){ int lst=g[u].back(); for(int x:g[u]){ nxt[u][lst]=x; lst=x; } } for(int u=1;u<=n;u++) for(int id:g[u])if(!us[u][id]){ int x=id,y=u; ++cnt; f[cnt]=cnt; while(!us[y][x]){ us[y][x]=1; add(x,cnt); y=p1(e[x])+p2(e[x])-y; x=nxt[y][x]; } } int lst=0; while(q--){ char op; int x,y; cin>>op>>x>>y; x^=lst,y^=lst; //cout<<op<<" "<<x<<" "<<y<<endl; if(op=='-'){ int ID=id[{x,y}]; if(del(ID)){ ++cb; vector<int>U,V; queue<int>qu,qv; qu.push(x); qv.push(y); U.push_back(x); V.push_back(y); ins[x]=ins[y]=1; while(1){ if(qv.empty()){ for(int u:U) ins[u]=0; for(int v:V) ins[v]=0,bel[v]=cb; break; } if(qu.empty()){ for(int u:U) ins[u]=0,bel[u]=cb; for(int v:V) ins[v]=0; break; } int u=qu.front(); qu.pop(); int v=qv.front(); qv.pop(); for(int id:g[u])if(!D[id]){ int v=p1(e[id])+p2(e[id])-u; if(!ins[v]){ qu.push(v); U.push_back(v); ins[v]=1; } } for(int id:g[v])if(!D[id]){ int u=p1(e[id])+p2(e[id])-v; if(!ins[u]){ qv.push(u); V.push_back(u); ins[u]=1; } } } } cout<<(lst=res)<<endl; } else cout<<(lst=(bel[x]==bel[y]))<<endl; } cout.flush(); return 0; } /* */