#import<bits/stdc++.h>
using namespace std;
const int N=101010;
vector<int>adj[N];
int pa[N];
int dfs(int i,int p)
{
pa[i]=p;
int sz=1;
pair<int,int>mx={0,0};
for(int t=0;t<(int)adj[i].size();t++)
{
int j=adj[i][t];
if(j==p)
continue;
int x=dfs(j,i);
sz+=x;
mx=max(mx,{x,t});
}
swap(adj[i][0],adj[i][mx.second]);
return sz;
}
int timer=1;
int nr[N],head[N],tail[N];
void hld(int i,int p,int h)
{
nr[i]=timer++;
head[i]=h;
tail[h]=i;
for(int t=0;t<adj[i].size();t++)
{
int j=adj[i][t];
if(j!=p)
hld(j,i,t==0?h:j);
}
}
struct line
{
int cc=0,cd=N,dd=0,dc=N;
int mn(int c)
{
if(c)
return min({cd,cc,dc+1,dd+1});
else
return min({cd+1,cc+1,dc,dd});
}
};
line merge(line a,line b)
{
line c;
c.cc=min({a.cc+b.cc,a.cc+b.dc+1,a.cd+b.cc+1,a.cd+b.dc});
c.cd=min({a.cc+b.cd,a.cc+b.dd+1,a.cd+b.cd+1,a.cd+b.dd});
c.dd=min({a.dc+b.cd,a.dc+b.dd+1,a.dd+b.cd+1,a.dd+b.dd});
c.dc=min({a.dc+b.cc,a.dc+b.dc+1,a.dd+b.cc+1,a.dd+b.dc});
return c;
}
struct ST
{
line X;
int l,r;
ST*left,*right;
ST(int l,int r):l(l),r(r)
{
if(l<r)
{
left=new ST(l,(l+r)/2);
right=new ST((l+r)/2+1,r);
X=merge(left->X,right->X);
}
}
line get(int x,int y)
{
if(x<=l&&r<=y)
return X;
if(r<x||y<l)
return line();
return merge(left->get(x,y),right->get(x,y));
}
void set(int x,int w,int c)
{
if(l==r)
{
if(c)
X.cc=w;
else
X.dd=w;
}
else
{
if(x<=(l+r)/2)
left->set(x,w,c);
else
right->set(x,w,c);
X=merge(left->X,right->X);
}
}
}medis(0,N);
void initialize(int N,vector<int>A,vector<int>B)
{
for(int i=0;i<N-1;i++)
{
adj[A[i]].push_back(B[i]);
adj[B[i]].push_back(A[i]);
}
dfs(1,0);
hld(1,0,1);
}
int C[N],D[N],V[N];
int fix(int v,int p)
{
V[v]=p;
while(true)
{
int w=head[v];
line X=medis.get(nr[w],nr[tail[w]]);
C[pa[w]]-=X.mn(1);
D[pa[w]]-=X.mn(0);
medis.set(nr[v],V[v]==1?N:C[v],1);
medis.set(nr[v],V[v]==2?N:D[v],0);
X=medis.get(nr[w],nr[tail[w]]);
C[pa[w]]+=X.mn(1);
D[pa[w]]+=X.mn(0);
if(v==1)break;
if(v!=w)
v=w;
else
v=pa[v];
}
return min(C[0],D[0]);
}
int cat(int v)
{
return fix(v,2);
}
int dog(int v)
{
return fix(v,1);
}
int neighbor(int v)
{
return fix(v,0);
}
Compilation message
catdog.cpp:1:2: warning: #import is a deprecated GCC extension [-Wdeprecated]
#import<bits/stdc++.h>
^~~~~~
catdog.cpp: In function 'void hld(int, int, int)':
catdog.cpp:30:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int t=0;t<adj[i].size();t++)
~^~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
18 ms |
12280 KB |
Output is correct |
2 |
Correct |
19 ms |
12408 KB |
Output is correct |
3 |
Correct |
19 ms |
12152 KB |
Output is correct |
4 |
Correct |
19 ms |
12280 KB |
Output is correct |
5 |
Correct |
19 ms |
12152 KB |
Output is correct |
6 |
Correct |
18 ms |
12152 KB |
Output is correct |
7 |
Correct |
19 ms |
12152 KB |
Output is correct |
8 |
Correct |
19 ms |
12228 KB |
Output is correct |
9 |
Correct |
18 ms |
12152 KB |
Output is correct |
10 |
Correct |
18 ms |
12152 KB |
Output is correct |
11 |
Correct |
18 ms |
12280 KB |
Output is correct |
12 |
Correct |
18 ms |
12152 KB |
Output is correct |
13 |
Correct |
24 ms |
12152 KB |
Output is correct |
14 |
Correct |
19 ms |
12228 KB |
Output is correct |
15 |
Correct |
19 ms |
12280 KB |
Output is correct |
16 |
Correct |
19 ms |
12280 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
18 ms |
12280 KB |
Output is correct |
2 |
Correct |
19 ms |
12408 KB |
Output is correct |
3 |
Correct |
19 ms |
12152 KB |
Output is correct |
4 |
Correct |
19 ms |
12280 KB |
Output is correct |
5 |
Correct |
19 ms |
12152 KB |
Output is correct |
6 |
Correct |
18 ms |
12152 KB |
Output is correct |
7 |
Correct |
19 ms |
12152 KB |
Output is correct |
8 |
Correct |
19 ms |
12228 KB |
Output is correct |
9 |
Correct |
18 ms |
12152 KB |
Output is correct |
10 |
Correct |
18 ms |
12152 KB |
Output is correct |
11 |
Correct |
18 ms |
12280 KB |
Output is correct |
12 |
Correct |
18 ms |
12152 KB |
Output is correct |
13 |
Correct |
24 ms |
12152 KB |
Output is correct |
14 |
Correct |
19 ms |
12228 KB |
Output is correct |
15 |
Correct |
19 ms |
12280 KB |
Output is correct |
16 |
Correct |
19 ms |
12280 KB |
Output is correct |
17 |
Correct |
24 ms |
12280 KB |
Output is correct |
18 |
Correct |
24 ms |
12280 KB |
Output is correct |
19 |
Correct |
21 ms |
12280 KB |
Output is correct |
20 |
Correct |
18 ms |
12280 KB |
Output is correct |
21 |
Correct |
21 ms |
12280 KB |
Output is correct |
22 |
Correct |
21 ms |
12280 KB |
Output is correct |
23 |
Correct |
25 ms |
12280 KB |
Output is correct |
24 |
Correct |
24 ms |
12280 KB |
Output is correct |
25 |
Correct |
23 ms |
12280 KB |
Output is correct |
26 |
Correct |
20 ms |
12280 KB |
Output is correct |
27 |
Correct |
20 ms |
12280 KB |
Output is correct |
28 |
Correct |
19 ms |
12280 KB |
Output is correct |
29 |
Correct |
22 ms |
12280 KB |
Output is correct |
30 |
Correct |
20 ms |
12280 KB |
Output is correct |
31 |
Correct |
19 ms |
12280 KB |
Output is correct |
32 |
Correct |
21 ms |
12280 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
18 ms |
12280 KB |
Output is correct |
2 |
Correct |
19 ms |
12408 KB |
Output is correct |
3 |
Correct |
19 ms |
12152 KB |
Output is correct |
4 |
Correct |
19 ms |
12280 KB |
Output is correct |
5 |
Correct |
19 ms |
12152 KB |
Output is correct |
6 |
Correct |
18 ms |
12152 KB |
Output is correct |
7 |
Correct |
19 ms |
12152 KB |
Output is correct |
8 |
Correct |
19 ms |
12228 KB |
Output is correct |
9 |
Correct |
18 ms |
12152 KB |
Output is correct |
10 |
Correct |
18 ms |
12152 KB |
Output is correct |
11 |
Correct |
18 ms |
12280 KB |
Output is correct |
12 |
Correct |
18 ms |
12152 KB |
Output is correct |
13 |
Correct |
24 ms |
12152 KB |
Output is correct |
14 |
Correct |
19 ms |
12228 KB |
Output is correct |
15 |
Correct |
19 ms |
12280 KB |
Output is correct |
16 |
Correct |
19 ms |
12280 KB |
Output is correct |
17 |
Correct |
24 ms |
12280 KB |
Output is correct |
18 |
Correct |
24 ms |
12280 KB |
Output is correct |
19 |
Correct |
21 ms |
12280 KB |
Output is correct |
20 |
Correct |
18 ms |
12280 KB |
Output is correct |
21 |
Correct |
21 ms |
12280 KB |
Output is correct |
22 |
Correct |
21 ms |
12280 KB |
Output is correct |
23 |
Correct |
25 ms |
12280 KB |
Output is correct |
24 |
Correct |
24 ms |
12280 KB |
Output is correct |
25 |
Correct |
23 ms |
12280 KB |
Output is correct |
26 |
Correct |
20 ms |
12280 KB |
Output is correct |
27 |
Correct |
20 ms |
12280 KB |
Output is correct |
28 |
Correct |
19 ms |
12280 KB |
Output is correct |
29 |
Correct |
22 ms |
12280 KB |
Output is correct |
30 |
Correct |
20 ms |
12280 KB |
Output is correct |
31 |
Correct |
19 ms |
12280 KB |
Output is correct |
32 |
Correct |
21 ms |
12280 KB |
Output is correct |
33 |
Correct |
1016 ms |
17144 KB |
Output is correct |
34 |
Correct |
276 ms |
17272 KB |
Output is correct |
35 |
Correct |
929 ms |
16240 KB |
Output is correct |
36 |
Correct |
1441 ms |
20444 KB |
Output is correct |
37 |
Correct |
41 ms |
14712 KB |
Output is correct |
38 |
Correct |
1573 ms |
21180 KB |
Output is correct |
39 |
Correct |
1593 ms |
21188 KB |
Output is correct |
40 |
Correct |
1552 ms |
21604 KB |
Output is correct |
41 |
Correct |
1559 ms |
21672 KB |
Output is correct |
42 |
Correct |
1437 ms |
21608 KB |
Output is correct |
43 |
Correct |
1451 ms |
21560 KB |
Output is correct |
44 |
Correct |
1428 ms |
21572 KB |
Output is correct |
45 |
Correct |
1431 ms |
21576 KB |
Output is correct |
46 |
Correct |
1499 ms |
21316 KB |
Output is correct |
47 |
Correct |
1738 ms |
21320 KB |
Output is correct |
48 |
Correct |
362 ms |
18496 KB |
Output is correct |
49 |
Correct |
398 ms |
19716 KB |
Output is correct |
50 |
Correct |
171 ms |
14328 KB |
Output is correct |
51 |
Correct |
175 ms |
15448 KB |
Output is correct |
52 |
Correct |
82 ms |
14072 KB |
Output is correct |
53 |
Correct |
642 ms |
20116 KB |
Output is correct |
54 |
Correct |
542 ms |
16052 KB |
Output is correct |
55 |
Correct |
1338 ms |
18956 KB |
Output is correct |
56 |
Correct |
921 ms |
16620 KB |
Output is correct |
57 |
Correct |
1020 ms |
19776 KB |
Output is correct |
58 |
Correct |
65 ms |
15476 KB |
Output is correct |
59 |
Correct |
164 ms |
15224 KB |
Output is correct |
60 |
Correct |
333 ms |
18868 KB |
Output is correct |
61 |
Correct |
372 ms |
19168 KB |
Output is correct |
62 |
Correct |
211 ms |
17904 KB |
Output is correct |
63 |
Correct |
123 ms |
18548 KB |
Output is correct |
64 |
Correct |
125 ms |
20216 KB |
Output is correct |
65 |
Correct |
136 ms |
24452 KB |
Output is correct |
66 |
Correct |
235 ms |
15484 KB |
Output is correct |
67 |
Correct |
191 ms |
21112 KB |
Output is correct |
68 |
Correct |
364 ms |
24524 KB |
Output is correct |
69 |
Correct |
131 ms |
13688 KB |
Output is correct |
70 |
Correct |
46 ms |
12408 KB |
Output is correct |
71 |
Correct |
191 ms |
18196 KB |
Output is correct |
72 |
Correct |
242 ms |
23068 KB |
Output is correct |
73 |
Correct |
509 ms |
27512 KB |
Output is correct |
74 |
Correct |
567 ms |
23672 KB |
Output is correct |
75 |
Correct |
440 ms |
27256 KB |
Output is correct |
76 |
Correct |
429 ms |
25848 KB |
Output is correct |
77 |
Correct |
557 ms |
24056 KB |
Output is correct |