#include "Joi.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int nx=1e4+5, mx=2e4+5, kx=60;
struct joi
{
int n, m, a[mx], b[mx], vl[kx], dsu[nx], res[nx], f, idx, vs[nx];
ll x;
vector<int> d[nx], fgroup;
vector<pair<int, int>> edg;
queue<pair<int, int>> q;
struct subgraph
{
int node[kx];
vector<int> g[kx];
} dp[nx];
int find(int x)
{
if (dsu[x]==x) return x;
return dsu[x]=find(dsu[x]);
}
void dfsfill(int u, int p)
{
vs[u]=1;
res[u]=idx++;
fgroup.push_back(u);
if (u!=p) edg.push_back({p, u});
for (auto v:d[u])
{
if (v==p) continue;
if (idx==kx) q.push({v, u}), vs[v]=1;
else dfsfill(v, u);
}
}
void build()
{
for (int i=0; i<kx; i++) vl[i]=x%2, x/=2;
for (int i=0; i<n; i++) dsu[i]=i;
for (int i=0; i<m; i++) if (find(a[i])!=find(b[i])) dsu[find(a[i])]=find(b[i]), d[a[i]].push_back(b[i]), d[b[i]].push_back(a[i]);
dfsfill(0, 0);
for (auto x:fgroup) for (auto e:edg) dp[x].g[res[e.first]].push_back(res[e.second]), dp[x].g[res[e.second]].push_back(res[e.first]);
for (auto x:fgroup) for (auto y:fgroup) dp[x].node[res[y]]=y;
while (!q.empty())
{
auto [u, p]=q.front();
q.pop();
int del;
for (int i=0; i<kx; i++) dp[u].node[i]=dp[p].node[i];
for (int i=0; i<kx; i++) if (dp[p].g[i].size()==1&&i!=p) del=i;
dp[u].node[del]=u;
dp[u].g[del].push_back(res[p]);
dp[u].g[res[p]].push_back(del);
for (int i=0; i<kx; i++) if (i!=del) for (auto j:dp[p].g[i]) if (j!=del) dp[u].g[i].push_back(j), dp[u].g[j].push_back(i);
for (auto v:d[u]) if (!vs[v]) q.push({v, u}), vs[v]=1;
}
for (int i=0; i<n; i++) MessageBoard(i, vl[res[i]]);
}
} J;
void Joi(int N, int M, int A[], int B[], long long X, int T) {
J.n=N, J.m=M;
for (int i=0; i<M; i++) J.a[i]=A[i], J.b[i]=B[i];
J.x=X;
J.build();
}
#include "Ioi.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int nxx=1e4+5, mxx=2e4+5, kxx=60;
struct ioi
{
int n, m, a[mxx], b[mxx], vl[kxx], dsu[nxx], res[nxx], f, idx, vs[nxx], st;
ll x, ans, pw[kxx];
vector<int> d[nxx], fgroup;
vector<pair<int, int>> edg;
queue<pair<int, int>> q;
struct subgraph
{
int node[kxx];
vector<int> g[kxx];
} dp[nxx];
int find(int x)
{
if (dsu[x]==x) return x;
return dsu[x]=find(dsu[x]);
}
void dfsfill(int u, int p)
{
vs[u]=1;
res[u]=idx++;
fgroup.push_back(u);
if (u!=p) edg.push_back({p, u});
for (auto v:d[u])
{
if (v==p) continue;
if (idx==kxx) q.push({v, u}), vs[v]=1;
else dfsfill(v, u);
}
}
void build()
{
pw[0]=1;
for (int i=1; i<kxx; i++) pw[i]=pw[i-1]*2;
for (int i=0; i<n; i++) dsu[i]=i;
for (int i=0; i<m; i++) if (find(a[i])!=find(b[i])) dsu[find(a[i])]=find(b[i]), d[a[i]].push_back(b[i]), d[b[i]].push_back(a[i]);
dfsfill(0, 0);
for (auto x:fgroup) for (auto e:edg) dp[x].g[res[e.first]].push_back(res[e.second]), dp[x].g[res[e.second]].push_back(res[e.first]);
//for (auto e:edg) if (e.first==0) cout<<"edge "<<e.first<<' '<<e.second<<'\n';
for (auto x:fgroup) for (auto y:fgroup) dp[x].node[res[y]]=y;
while (!q.empty())
{
auto [u, p]=q.front();
q.pop();
int del;
for (int i=0; i<kxx; i++) dp[u].node[i]=dp[p].node[i];
for (int i=0; i<kxx; i++) if (dp[p].g[i].size()==1&&i!=p) del=i;
dp[u].node[del]=u;
dp[u].g[del].push_back(res[p]);
dp[u].g[res[p]].push_back(del);
for (int i=0; i<kxx; i++) if (i!=del) for (auto j:dp[p].g[i]) if (j!=del) dp[u].g[i].push_back(j), dp[u].g[j].push_back(i);
for (auto v:d[u]) if (!vs[v]) q.push({v, u}), vs[v]=1;
}
}
void dfssolve(int u, int p, int rt)
{
for (auto v:dp[rt].g[u]) if (v!=p) vl[v]=Move(dp[rt].node[v]), dfssolve(v, u, rt);
if (p!=u) vl[p]=Move(dp[rt].node[p]);
}
ll solve()
{
int stcolor;
for (int i=0; i<kxx; i++) if (dp[st].node[i]==st) stcolor=i;
dfssolve(stcolor, stcolor, st);
for (int i=0; i<kxx; i++) ans+=vl[i]*pw[i];
return ans;
}
} I;
long long Ioi(int N, int M, int A[], int B[], int P, int V, int T) {
I.n=N, I.m=M;
for (int i=0; i<M; i++) I.a[i]=A[i], I.b[i]=B[i];
I.st=P;
I.build();
return I.solve();
}
Compilation message
Ioi.cpp: In function 'long long int Ioi(int, int, int*, int*, int, int, int)':
Ioi.cpp:66:80: warning: 'stcolor' may be used uninitialized in this function [-Wmaybe-uninitialized]
66 | for (auto v:dp[rt].g[u]) if (v!=p) vl[v]=Move(dp[rt].node[v]), dfssolve(v, u, rt);
| ~~~~~~~~^~~~~~~~~~
Ioi.cpp:71:13: note: 'stcolor' was declared here
71 | int stcolor;
| ^~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
34576 KB |
Output is correct |
| 2 |
Incorrect |
8 ms |
36124 KB |
Wrong Answer [7] |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
194 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
199 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
207 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
195 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
