#include "Joi.h" #include <bits/stdc++.h> #define ii pair<int, int> #define fi first #define se second #define inf 0x3f3f3f3f3f3f3f3f using namespace std; using ll = long long; const ll mod=1e9+7; const int nx=1e4+5; struct Jay { // void MessageBoard(int u, int v) // { // cout<<u<<' '<<v<<'\n'; // } vector<int> adj[nx], ve[nx]; bitset<nx> ed[nx]; queue<int> f; bool vis[nx]; int par[nx], deg[nx], id[nx]; void init(int n) { for(int i = 0; i < n; i++) { adj[i].clear(); ve[i].clear(); ed[i].reset(); while(f.size()) f.pop(); vis[i]=0; id[i]=0; par[i]=-1; deg[i]=0; } } int find(int u) { if(par[u]==-1) return u; return par[u]=find(par[u]); } bool join(int u, int v) { u=find(u); v=find(v); if(u==v) return 0; par[v]=u; return 1; } void joi(int n, int m, int a[], int b[], ll x, int t) { for(int i = 0; i < m; i++) { if(join(a[i], b[i])) { ed[a[i]][b[i]]=ed[b[i]][a[i]]=1; adj[a[i]].emplace_back(b[i]); adj[b[i]].emplace_back(a[i]); } } f.push(0); vis[0]=1; ve[0].emplace_back(0); while(f.size()) { int u=f.front(); f.pop(); for(int v:adj[u]) { if(ve[0].size()==60) break; if(!vis[v]) { ve[0].emplace_back(v); vis[v]=1; f.push(v); } } } if(ve[0].size()!=60) while(1); for(int i = 0; i < 60; i++) { id[ve[0][i]]=i; if(ve[0][i]!=0) ve[ve[0][i]]=ve[0]; } while(f.size()) f.pop(); for(int i = 0; i < n; i++) if(!vis[i]) f.push(i); while(f.size()) { int u=f.front(); f.pop(); for(int i = 0; i < 60; i++) for(int j = i+1; j < 60; j++) if(ed[ve[u][i]][ve[u][j]]) deg[ve[u][i]]++, deg[ve[u][j]]++; int nxt=-1; for(int i = 0; i < 60; i++) if(deg[ve[u][i]]==1 && ve[u][i]!=u) nxt=i; for(int v:adj[u]) { if(!vis[v]) { vis[v]=1; f.push(v); ve[v]=ve[u]; ve[v][nxt]=v; id[v]=nxt; } } } for(int i = 0; i < n; i++) MessageBoard(i, x>>id[i]&1); } } J; void Joi(int n, int m, int a[], int b[], ll x, int t) { J.init(n); J.joi(n, m, a, b, x, t); } // int main() // { // ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); // vector<int> l, r; // for(int i = 0; i < 59; i++) // l.emplace_back(i), r.emplace_back(i+1); // Joi(60, 59, l, r, 123, 1); // }

#include "Ioi.h" #include <bits/stdc++.h> #define ii pair<int, int> #define fi first #define se second #define inf 0x3f3f3f3f3f3f3f3f using namespace std; using ll = long long; const ll mod=1e9+7; const int nx=1e4+5; struct Ai { // int Move(int u) // { // return (123ll>>u&1); // } vector<int> adj[nx], ve[nx]; bitset<nx> ed[nx]; queue<int> f; bool vis[nx], ok[nx]; int par[nx], deg[nx], res[60], id[nx]; void init(int n) { for(int i = 0; i < n; i++) { adj[i].clear(); ve[i].clear(); ed[i].reset(); while(f.size()) f.pop(); vis[i]=0; id[i]=0; par[i]=-1; deg[i]=0; ok[i]=0; } } int find(int u) { if(par[u]==-1) return u; return par[u]=find(par[u]); } bool join(int u, int v) { u=find(u); v=find(v); if(u==v) return 0; par[v]=u; return 1; } void dfs(int u, int val) { res[id[u]]=val; vis[u]=1; for(int v:adj[u]) if(!vis[v] && ok[v]) dfs(v, Move(v)), Move(u); } ll ioi(int n, int m, int a[], int b[], int p, int val, int t) { for(int i = 0; i < m; i++) { if(join(a[i], b[i])) { ed[a[i]][b[i]]=ed[b[i]][a[i]]=1; adj[a[i]].emplace_back(b[i]); adj[b[i]].emplace_back(a[i]); } } f.push(0); vis[0]=1; ve[0].emplace_back(0); while(f.size()) { int u=f.front(); f.pop(); for(int v:adj[u]) { if(ve[0].size()==60) break; if(!vis[v]) { ve[0].emplace_back(v); vis[v]=1; f.push(v); } } } for(int i = 0; i < 60; i++) { id[ve[0][i]]=i; if(ve[0][i]!=0) ve[ve[0][i]]=ve[0]; } while(f.size()) f.pop(); for(int i = 0; i < n; i++) if(!vis[i]) f.push(i); while(f.size()) { int u=f.front(); f.pop(); for(int i = 0; i < 60; i++) for(int j = i+1; j < 60; j++) if(ed[ve[u][i]][ve[u][j]]) deg[ve[u][i]]++, deg[ve[u][j]]++; int nxt=-1; for(int i = 0; i < 60; i++) if(deg[ve[u][i]]==1 && ve[u][i]!=u) nxt=i; for(int v:adj[u]) { if(!vis[v]) { vis[v]=1; f.push(v); ve[v]=ve[u]; ve[v][nxt]=v; id[v]=nxt; } } } for(int u:ve[p]) ok[u]=1, vis[u]=0; dfs(p, val); ll ans=0; for(int i = 0; i < 60; i++) if(res[i]) ans|=(1ll<<i); return ans; } } I; ll Ioi(int n, int m, int a[], int b[], int p, int val, int t) { I.init(n); return I.ioi(n, m, a, b, p, val, t); } // int main() // { // ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); // vector<int> l, r; // for(int i = 0; i < 59; i++) // l.emplace_back(i), r.emplace_back(i+1); // cout<<Ioi(60, 59, l, r, 5, 1, 1); // }