#include "Joi.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
const int N=10050;
int n,m;
vector<int> E[N];
struct DSU
{
int p[N];
DSU(){}
int Find(int x){ return p[x]?p[x]=Find(p[x]):x;}
bool Same(int x, int y){ return Find(x)==Find(y);}
void Union(int x, int y){ p[Find(x)]=Find(y);}
} DS;
void AddEdge(int u, int v){ E[u].pb(v);E[v].pb(u);DS.Union(u,v);}
int bt[60],cnt,idx[N][60],csz[N],my[N],sgn[N],up[N];
int Groups(int u, int p, int sz=-1, int cmp=-1)
{
if(sz==-1) sz=60,cmp=cnt++;
sgn[u]=csz[cmp];
idx[cmp][csz[cmp]++]=u;
my[u]=cmp;
sz--;
for(int v:E[u]) if(v!=p)
{
if(sz>0) sz=Groups(v,u,sz,cmp);
else if(Groups(v,u)>0) up[my[v]]=u;
}
return sz;
}
int was[N];
vector<int> Take(int u, int sz, int mark)
{
queue<int> q;
q.push(u);
was[u]=mark;
vector<int> ans;
while(sz--)
{
int x=q.front();
q.pop();
ans.pb(x);
for(int y:E[x]) if(was[y]!=mark && my[y]==my[u])
{
was[y]=mark;
q.push(y);
}
}
return ans;
}
void Joi(int _n, int _m, int A[], int B[], ll X, int T)
{
n=_n;m=_m;
for(int i=0;i<m;i++) if(!DS.Same(A[i]+1,B[i]+1)) AddEdge(A[i]+1,B[i]+1);
for(int i=0;i<60;i++) bt[i]=X>>i&1;
Groups(1,0);
int mark=0;
for(int i=0;i<cnt;i++)
{
if(csz[i]<60)
{
vector<int> tmp=Take(up[i],60-csz[i],++mark);
vector<bool> ban(60,0);
for(int j:tmp) ban[sgn[j]]=1;
for(int j=0,ptr=0;j<csz[i];j++)
{
while(ban[ptr]) ptr++;
sgn[idx[i][j]]=ptr;
ban[ptr]=1;
}
}
}
for(int i=1;i<=n;i++) MessageBoard(i-1,bt[sgn[i]]);
}
#include "Ioi.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
const int N=10050;
int n,m;
vector<int> E[N];
struct DSU
{
int p[N];
DSU(){}
int Find(int x){ return p[x]?p[x]=Find(p[x]):x;}
bool Same(int x, int y){ return Find(x)==Find(y);}
void Union(int x, int y){ p[Find(x)]=Find(y);}
} DS;
void AddEdge(int u, int v){ E[u].pb(v);E[v].pb(u);DS.Union(u,v);}
int bt[60],cnt,idx[N][60],csz[N],my[N],sgn[N],up[N];
int Groups(int u, int p, int sz=-1, int cmp=-1)
{
if(sz==-1) sz=60,cmp=cnt++;
sgn[u]=csz[cmp];
idx[cmp][csz[cmp]++]=u;
my[u]=cmp;
sz--;
for(int v:E[u]) if(v!=p)
{
if(sz>0) sz=Groups(v,u,sz,cmp);
else if(Groups(v,u)>0) up[my[v]]=u;
}
return sz;
}
int was[N];
vector<int> Take(int u, int sz, int mark)
{
queue<int> q;
q.push(u);
was[u]=mark;
vector<int> ans;
while(sz--)
{
int x=q.front();
q.pop();
ans.pb(x);
for(int y:E[x]) if(was[y]!=mark && my[y]==my[u])
{
was[y]=mark;
q.push(y);
}
}
return ans;
}
bool use[N];
void Walk(int u, int p, bool Ask)
{
if(Ask) bt[sgn[u]]=Move(u-1);
for(int v:E[u]) if(v!=p && use[v])
{
Walk(v,u,1);
Move(u-1);
}
}
ll Ioi(int _n, int _m, int A[], int B[], int P, int V, int T)
{
n=_n;m=_m;
for(int i=0;i<m;i++) if(!DS.Same(A[i]+1,B[i]+1)) AddEdge(A[i]+1,B[i]+1);
Groups(1,0);
int mark=0;
for(int i=0;i<cnt;i++)
{
if(csz[i]<60)
{
vector<int> tmp=Take(up[i],60-csz[i],++mark);
vector<bool> ban(60,0);
for(int j:tmp) ban[sgn[j]]=1;
for(int j=0,ptr=0;j<csz[i];j++)
{
while(ban[ptr]) ptr++;
sgn[idx[i][j]]=ptr;
ban[ptr]=1;
}
}
}
bt[sgn[P+1]]=V;
vector<int> nodes;
if(csz[my[P+1]]<60)
{
nodes=Take(up[my[P+1]],60-csz[my[P+1]],++mark);
}
for(int i=0;i<csz[my[P+1]];i++) nodes.pb(idx[my[P+1]][i]);
for(int u:nodes) use[u]=1;
Walk(P+1,0,0);
ll X=0;
for(int i=0;i<60;i++) X+=(ll)bt[i]<<i;
return X;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
1268 KB |
Output is correct |
2 |
Correct |
4 ms |
1400 KB |
Output is correct |
3 |
Correct |
4 ms |
1360 KB |
Output is correct |
4 |
Correct |
4 ms |
1344 KB |
Output is correct |
5 |
Correct |
4 ms |
1472 KB |
Output is correct |
6 |
Correct |
5 ms |
1340 KB |
Output is correct |
7 |
Correct |
4 ms |
1404 KB |
Output is correct |
8 |
Correct |
6 ms |
1404 KB |
Output is correct |
9 |
Correct |
5 ms |
1412 KB |
Output is correct |
10 |
Correct |
5 ms |
1376 KB |
Output is correct |
11 |
Correct |
7 ms |
1664 KB |
Output is correct |
12 |
Correct |
4 ms |
1268 KB |
Output is correct |
13 |
Correct |
4 ms |
1440 KB |
Output is correct |
14 |
Correct |
5 ms |
1404 KB |
Output is correct |
15 |
Correct |
5 ms |
1404 KB |
Output is correct |
16 |
Correct |
5 ms |
1452 KB |
Output is correct |
17 |
Correct |
5 ms |
1412 KB |
Output is correct |
18 |
Correct |
5 ms |
1412 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
36 ms |
4528 KB |
Output is correct |
2 |
Correct |
35 ms |
4460 KB |
Output is correct |
3 |
Correct |
38 ms |
4360 KB |
Output is correct |
4 |
Correct |
25 ms |
3488 KB |
Output is correct |
5 |
Correct |
25 ms |
4248 KB |
Output is correct |
6 |
Correct |
31 ms |
4504 KB |
Output is correct |
7 |
Correct |
30 ms |
4504 KB |
Output is correct |
8 |
Correct |
28 ms |
4376 KB |
Output is correct |
9 |
Correct |
30 ms |
4512 KB |
Output is correct |
10 |
Correct |
344 ms |
7484 KB |
Output is correct |
11 |
Correct |
345 ms |
7652 KB |
Output is correct |
12 |
Correct |
20 ms |
3200 KB |
Output is correct |
13 |
Correct |
19 ms |
3236 KB |
Output is correct |
14 |
Correct |
20 ms |
3212 KB |
Output is correct |
15 |
Correct |
28 ms |
3740 KB |
Output is correct |
16 |
Correct |
28 ms |
3740 KB |
Output is correct |
17 |
Correct |
24 ms |
3736 KB |
Output is correct |
18 |
Correct |
26 ms |
3736 KB |
Output is correct |
19 |
Correct |
25 ms |
3740 KB |
Output is correct |
20 |
Correct |
17 ms |
3992 KB |
Output is correct |
21 |
Correct |
17 ms |
3872 KB |
Output is correct |
22 |
Correct |
36 ms |
4760 KB |
Output is correct |
23 |
Correct |
37 ms |
5144 KB |
Output is correct |
24 |
Correct |
37 ms |
5024 KB |
Output is correct |
25 |
Correct |
36 ms |
4888 KB |
Output is correct |
26 |
Correct |
36 ms |
5016 KB |
Output is correct |
27 |
Correct |
37 ms |
4976 KB |
Output is correct |
28 |
Correct |
37 ms |
5152 KB |
Output is correct |
29 |
Correct |
36 ms |
4748 KB |
Output is correct |
30 |
Correct |
35 ms |
5008 KB |
Output is correct |
31 |
Correct |
4 ms |
1488 KB |
Output is correct |
32 |
Correct |
4 ms |
1272 KB |
Output is correct |
33 |
Correct |
6 ms |
1404 KB |
Output is correct |
34 |
Correct |
4 ms |
1396 KB |
Output is correct |
35 |
Correct |
4 ms |
1320 KB |
Output is correct |
36 |
Correct |
4 ms |
1268 KB |
Output is correct |
37 |
Correct |
4 ms |
1268 KB |
Output is correct |
38 |
Correct |
4 ms |
1268 KB |
Output is correct |
39 |
Correct |
4 ms |
1268 KB |
Output is correct |
40 |
Correct |
4 ms |
1432 KB |
Output is correct |
41 |
Correct |
4 ms |
1396 KB |
Output is correct |
42 |
Correct |
4 ms |
1476 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
1276 KB |
Output is correct |
2 |
Correct |
4 ms |
1396 KB |
Output is correct |
3 |
Correct |
6 ms |
1396 KB |
Output is correct |
4 |
Correct |
6 ms |
1952 KB |
Output is correct |
5 |
Correct |
6 ms |
1824 KB |
Output is correct |
6 |
Correct |
8 ms |
1824 KB |
Output is correct |
7 |
Correct |
8 ms |
2080 KB |
Output is correct |
8 |
Correct |
7 ms |
1960 KB |
Output is correct |
9 |
Correct |
17 ms |
4632 KB |
Output is correct |
10 |
Correct |
17 ms |
4768 KB |
Output is correct |
11 |
Correct |
18 ms |
4760 KB |
Output is correct |
12 |
Correct |
6 ms |
1348 KB |
Output is correct |
13 |
Correct |
4 ms |
1396 KB |
Output is correct |
14 |
Correct |
4 ms |
1276 KB |
Output is correct |
15 |
Correct |
4 ms |
1396 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
35 ms |
4480 KB |
Output is correct |
2 |
Correct |
36 ms |
4480 KB |
Output is correct |
3 |
Correct |
36 ms |
4476 KB |
Output is correct |
4 |
Correct |
24 ms |
3712 KB |
Output is correct |
5 |
Correct |
25 ms |
4504 KB |
Output is correct |
6 |
Correct |
30 ms |
4520 KB |
Output is correct |
7 |
Correct |
28 ms |
4528 KB |
Output is correct |
8 |
Correct |
30 ms |
4308 KB |
Output is correct |
9 |
Correct |
30 ms |
4384 KB |
Output is correct |
10 |
Correct |
339 ms |
7584 KB |
Output is correct |
11 |
Correct |
393 ms |
7776 KB |
Output is correct |
12 |
Correct |
20 ms |
3272 KB |
Output is correct |
13 |
Correct |
20 ms |
3220 KB |
Output is correct |
14 |
Correct |
22 ms |
3448 KB |
Output is correct |
15 |
Correct |
30 ms |
3744 KB |
Output is correct |
16 |
Correct |
32 ms |
3668 KB |
Output is correct |
17 |
Correct |
26 ms |
3740 KB |
Output is correct |
18 |
Correct |
25 ms |
3748 KB |
Output is correct |
19 |
Correct |
25 ms |
3608 KB |
Output is correct |
20 |
Correct |
17 ms |
4000 KB |
Output is correct |
21 |
Correct |
17 ms |
4056 KB |
Output is correct |
22 |
Correct |
37 ms |
5132 KB |
Output is correct |
23 |
Correct |
37 ms |
5024 KB |
Output is correct |
24 |
Correct |
36 ms |
5016 KB |
Output is correct |
25 |
Correct |
36 ms |
5260 KB |
Output is correct |
26 |
Correct |
37 ms |
5080 KB |
Output is correct |
27 |
Correct |
36 ms |
5272 KB |
Output is correct |
28 |
Correct |
36 ms |
4888 KB |
Output is correct |
29 |
Correct |
34 ms |
4608 KB |
Output is correct |
30 |
Correct |
35 ms |
5004 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
38 ms |
4452 KB |
Output is correct |
2 |
Correct |
37 ms |
4512 KB |
Output is correct |
3 |
Correct |
36 ms |
4480 KB |
Output is correct |
4 |
Correct |
24 ms |
3608 KB |
Output is correct |
5 |
Correct |
25 ms |
4632 KB |
Output is correct |
6 |
Correct |
30 ms |
4504 KB |
Output is correct |
7 |
Correct |
28 ms |
4120 KB |
Output is correct |
8 |
Correct |
32 ms |
4640 KB |
Output is correct |
9 |
Correct |
33 ms |
4800 KB |
Output is correct |
10 |
Correct |
346 ms |
7620 KB |
Output is correct |
11 |
Correct |
339 ms |
7652 KB |
Output is correct |
12 |
Correct |
20 ms |
3200 KB |
Output is correct |
13 |
Correct |
19 ms |
3208 KB |
Output is correct |
14 |
Correct |
20 ms |
3264 KB |
Output is correct |
15 |
Correct |
27 ms |
3608 KB |
Output is correct |
16 |
Correct |
27 ms |
3736 KB |
Output is correct |
17 |
Correct |
25 ms |
3736 KB |
Output is correct |
18 |
Correct |
25 ms |
3616 KB |
Output is correct |
19 |
Correct |
25 ms |
3720 KB |
Output is correct |
20 |
Correct |
17 ms |
3864 KB |
Output is correct |
21 |
Correct |
17 ms |
4060 KB |
Output is correct |
22 |
Correct |
37 ms |
5124 KB |
Output is correct |
23 |
Correct |
37 ms |
5256 KB |
Output is correct |
24 |
Correct |
36 ms |
5092 KB |
Output is correct |
25 |
Correct |
35 ms |
4924 KB |
Output is correct |
26 |
Correct |
37 ms |
4888 KB |
Output is correct |
27 |
Correct |
37 ms |
5456 KB |
Output is correct |
28 |
Correct |
37 ms |
5284 KB |
Output is correct |
29 |
Correct |
33 ms |
4884 KB |
Output is correct |
30 |
Correct |
35 ms |
5080 KB |
Output is correct |
31 |
Correct |
4 ms |
1468 KB |
Output is correct |
32 |
Correct |
5 ms |
1268 KB |
Output is correct |
33 |
Correct |
6 ms |
1404 KB |
Output is correct |
34 |
Correct |
4 ms |
1468 KB |
Output is correct |
35 |
Correct |
4 ms |
1268 KB |
Output is correct |
36 |
Correct |
4 ms |
1396 KB |
Output is correct |
37 |
Correct |
4 ms |
1396 KB |
Output is correct |
38 |
Correct |
4 ms |
1268 KB |
Output is correct |
39 |
Correct |
4 ms |
1516 KB |
Output is correct |
40 |
Correct |
4 ms |
1396 KB |
Output is correct |
41 |
Correct |
4 ms |
1472 KB |
Output is correct |
42 |
Correct |
4 ms |
1404 KB |
Output is correct |