#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;
int t=0;
for(int j:adj[i])
{
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>
^~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
19 ms |
12196 KB |
Output is correct |
2 |
Correct |
18 ms |
12152 KB |
Output is correct |
3 |
Correct |
20 ms |
12152 KB |
Output is correct |
4 |
Correct |
19 ms |
12152 KB |
Output is correct |
5 |
Correct |
22 ms |
12252 KB |
Output is correct |
6 |
Correct |
19 ms |
12152 KB |
Output is correct |
7 |
Correct |
19 ms |
12152 KB |
Output is correct |
8 |
Correct |
19 ms |
12152 KB |
Output is correct |
9 |
Correct |
19 ms |
12152 KB |
Output is correct |
10 |
Correct |
18 ms |
12152 KB |
Output is correct |
11 |
Correct |
18 ms |
12152 KB |
Output is correct |
12 |
Correct |
19 ms |
12152 KB |
Output is correct |
13 |
Correct |
18 ms |
12152 KB |
Output is correct |
14 |
Correct |
19 ms |
12152 KB |
Output is correct |
15 |
Correct |
19 ms |
12152 KB |
Output is correct |
16 |
Correct |
19 ms |
12280 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
19 ms |
12196 KB |
Output is correct |
2 |
Correct |
18 ms |
12152 KB |
Output is correct |
3 |
Correct |
20 ms |
12152 KB |
Output is correct |
4 |
Correct |
19 ms |
12152 KB |
Output is correct |
5 |
Correct |
22 ms |
12252 KB |
Output is correct |
6 |
Correct |
19 ms |
12152 KB |
Output is correct |
7 |
Correct |
19 ms |
12152 KB |
Output is correct |
8 |
Correct |
19 ms |
12152 KB |
Output is correct |
9 |
Correct |
19 ms |
12152 KB |
Output is correct |
10 |
Correct |
18 ms |
12152 KB |
Output is correct |
11 |
Correct |
18 ms |
12152 KB |
Output is correct |
12 |
Correct |
19 ms |
12152 KB |
Output is correct |
13 |
Correct |
18 ms |
12152 KB |
Output is correct |
14 |
Correct |
19 ms |
12152 KB |
Output is correct |
15 |
Correct |
19 ms |
12152 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 |
12408 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 |
12328 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 |
19 ms |
12280 KB |
Output is correct |
28 |
Correct |
19 ms |
12280 KB |
Output is correct |
29 |
Correct |
22 ms |
12408 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 |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
19 ms |
12196 KB |
Output is correct |
2 |
Correct |
18 ms |
12152 KB |
Output is correct |
3 |
Correct |
20 ms |
12152 KB |
Output is correct |
4 |
Correct |
19 ms |
12152 KB |
Output is correct |
5 |
Correct |
22 ms |
12252 KB |
Output is correct |
6 |
Correct |
19 ms |
12152 KB |
Output is correct |
7 |
Correct |
19 ms |
12152 KB |
Output is correct |
8 |
Correct |
19 ms |
12152 KB |
Output is correct |
9 |
Correct |
19 ms |
12152 KB |
Output is correct |
10 |
Correct |
18 ms |
12152 KB |
Output is correct |
11 |
Correct |
18 ms |
12152 KB |
Output is correct |
12 |
Correct |
19 ms |
12152 KB |
Output is correct |
13 |
Correct |
18 ms |
12152 KB |
Output is correct |
14 |
Correct |
19 ms |
12152 KB |
Output is correct |
15 |
Correct |
19 ms |
12152 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 |
12408 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 |
12328 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 |
19 ms |
12280 KB |
Output is correct |
28 |
Correct |
19 ms |
12280 KB |
Output is correct |
29 |
Correct |
22 ms |
12408 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 |
985 ms |
17280 KB |
Output is correct |
34 |
Correct |
266 ms |
17272 KB |
Output is correct |
35 |
Correct |
940 ms |
16360 KB |
Output is correct |
36 |
Correct |
1601 ms |
20524 KB |
Output is correct |
37 |
Correct |
45 ms |
14712 KB |
Output is correct |
38 |
Correct |
1816 ms |
21316 KB |
Output is correct |
39 |
Correct |
1657 ms |
21696 KB |
Output is correct |
40 |
Correct |
1558 ms |
21700 KB |
Output is correct |
41 |
Correct |
1550 ms |
21788 KB |
Output is correct |
42 |
Correct |
1536 ms |
21708 KB |
Output is correct |
43 |
Correct |
1463 ms |
21716 KB |
Output is correct |
44 |
Correct |
1414 ms |
22092 KB |
Output is correct |
45 |
Correct |
1419 ms |
22088 KB |
Output is correct |
46 |
Correct |
1473 ms |
22084 KB |
Output is correct |
47 |
Correct |
1524 ms |
22084 KB |
Output is correct |
48 |
Correct |
357 ms |
19132 KB |
Output is correct |
49 |
Correct |
375 ms |
20768 KB |
Output is correct |
50 |
Correct |
164 ms |
14348 KB |
Output is correct |
51 |
Correct |
170 ms |
15560 KB |
Output is correct |
52 |
Correct |
77 ms |
13960 KB |
Output is correct |
53 |
Correct |
601 ms |
20888 KB |
Output is correct |
54 |
Correct |
505 ms |
16368 KB |
Output is correct |
55 |
Correct |
1311 ms |
19796 KB |
Output is correct |
56 |
Correct |
856 ms |
17212 KB |
Output is correct |
57 |
Correct |
1037 ms |
20792 KB |
Output is correct |
58 |
Correct |
66 ms |
15476 KB |
Output is correct |
59 |
Correct |
162 ms |
15480 KB |
Output is correct |
60 |
Correct |
325 ms |
19960 KB |
Output is correct |
61 |
Correct |
364 ms |
20192 KB |
Output is correct |
62 |
Correct |
210 ms |
18328 KB |
Output is correct |
63 |
Correct |
117 ms |
18800 KB |
Output is correct |
64 |
Correct |
122 ms |
20536 KB |
Output is correct |
65 |
Correct |
134 ms |
24992 KB |
Output is correct |
66 |
Correct |
232 ms |
15736 KB |
Output is correct |
67 |
Correct |
175 ms |
21240 KB |
Output is correct |
68 |
Correct |
359 ms |
25208 KB |
Output is correct |
69 |
Correct |
131 ms |
13712 KB |
Output is correct |
70 |
Correct |
47 ms |
12408 KB |
Output is correct |
71 |
Correct |
189 ms |
18552 KB |
Output is correct |
72 |
Correct |
242 ms |
23544 KB |
Output is correct |
73 |
Correct |
513 ms |
28520 KB |
Output is correct |
74 |
Correct |
553 ms |
24952 KB |
Output is correct |
75 |
Correct |
422 ms |
28536 KB |
Output is correct |
76 |
Correct |
426 ms |
27228 KB |
Output is correct |
77 |
Correct |
549 ms |
25308 KB |
Output is correct |