#include "catdog.h"
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const ll INF=INT_MAX/3;
ll mmax=101010;
ll N,Q;
ll catdog[101010];
vector <ll> graph[101010];
priority_queue <pair<ll,ll> > pq[101010];
ll num[101010];
ll group[101010];
ll go[101010];
ll cnt,gnn,gtt;
struct node{
ll val[2][2];
void init(){
val[0][0]=val[1][1]=0;
val[0][1]=val[1][0]=INF;
}
void update(node a,node b){
for(ll i=0;i<2;i++)fill(val[i],val[i]+2,INF);
//puts("filled");
for(ll i=0;i<2;i++)for(ll j=0;j<2;j++)
for(ll x=0;x<2;x++)for(ll y=0;y<2;y++)//fuuuujkkkkk;
val[i][y]=min(val[i][y],a.val[i][j]+b.val[x][y]+(j^x));
//puts("hmmteresting");
//puts("fucking bald arn...");
}
};
struct SEG{
vector <node> tree;
ll sz;
void trit(ll l,ll r,ll m){
//printf("%lld %lld %lld\n",l,r,m);
if(l==r){
tree[m].init();
return;
}
ll mid=(l+r)/2;
trit(l,mid,m*2);
trit(mid+1,r,m*2+1);
tree[m].update(tree[m*2],tree[m*2+1]);
//printf("updated\n");
}
void init(ll n){
sz=n;
tree.resize(n*4);
if(sz)trit(1,sz,1);
}
void update(ll x,ll l,ll r,ll m,ll a,ll b){
if(x<l||x>r)return;
if(l==r){
tree[m].val[0][0]+=a;
tree[m].val[1][1]+=b;
return;
}
ll mid=(l+r)/2;
update(x,l,mid,m*2,a,b);
update(x,mid+1,r,m*2+1,a,b);
tree[m].update(tree[m*2],tree[m*2+1]);
}
pair<ll,ll> getf(){
ll a=min(tree[1].val[0][0],tree[1].val[0][1]);
ll b=min(tree[1].val[1][0],tree[1].val[1][1]);
return {min(a,b+1),min(a+1,b)};
}
};
SEG HLD[101010];
ll dfs1(ll now,ll par){
//printf("%lld\n",now);
for(auto i:graph[now])if(i!=par){
num[now]+=dfs1(i,now);
pq[now].push({num[i],i});
}
return ++num[now];
}
void dfs2(ll now,ll par){
if(!gnn){
gnn=++gtt;
go[gnn]=par;
}
group[now]=gnn;
num[now]=++cnt;
while(!pq[now].empty()){
dfs2(pq[now].top().second,now);
pq[now].top();
pq[now].pop();
}
HLD[gnn].init(cnt);
gnn=0;cnt=0;
//printf("%lld\n",now);
}
void initialize(int n,vector<int> A,vector<int> B) {
N=n;
for(int i=0;i<A.size();i++)graph[A[i]].push_back(B[i]);
for(int i=0;i<A.size();i++)graph[B[i]].push_back(A[i]);
dfs1(1,0);
dfs2(1,0);
}
void hldupdate(ll now,ll a,ll b){
while(now){
//printf("%lld\n",now);
pair<ll,ll> p=HLD[group[now]].getf();
HLD[group[now]].update(num[now],1,HLD[group[now]].sz,1,a,b);
pair<ll,ll> q=HLD[group[now]].getf();
a=q.first-p.first;
b=q.second-p.second;
now=go[group[now]];
}
}
int cat(int v){
hldupdate(v,mmax,0);
catdog[v]=1;
return min(HLD[1].getf().first,HLD[1].getf().second);
}
int dog(int v){
hldupdate(v,0,mmax);
catdog[v]=2;
return min(HLD[1].getf().first,HLD[1].getf().second);
}
int neighbor(int v){
if(catdog[v]==1)hldupdate(v,-mmax,0);
else hldupdate(v,0,-mmax);
catdog[v]=0;
return min(HLD[1].getf().first,HLD[1].getf().second);
}
Compilation message
catdog.cpp: In function 'void initialize(int, std::vector<int>, std::vector<int>)':
catdog.cpp:96:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<A.size();i++)graph[A[i]].push_back(B[i]);
~^~~~~~~~~
catdog.cpp:97:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<A.size();i++)graph[B[i]].push_back(A[i]);
~^~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
11 ms |
9080 KB |
Output is correct |
2 |
Correct |
10 ms |
9080 KB |
Output is correct |
3 |
Correct |
11 ms |
9112 KB |
Output is correct |
4 |
Correct |
10 ms |
9080 KB |
Output is correct |
5 |
Correct |
10 ms |
9080 KB |
Output is correct |
6 |
Correct |
10 ms |
9080 KB |
Output is correct |
7 |
Correct |
12 ms |
9080 KB |
Output is correct |
8 |
Correct |
11 ms |
9080 KB |
Output is correct |
9 |
Correct |
11 ms |
9080 KB |
Output is correct |
10 |
Correct |
11 ms |
9080 KB |
Output is correct |
11 |
Correct |
11 ms |
9080 KB |
Output is correct |
12 |
Correct |
10 ms |
9080 KB |
Output is correct |
13 |
Correct |
11 ms |
9080 KB |
Output is correct |
14 |
Correct |
10 ms |
9080 KB |
Output is correct |
15 |
Correct |
11 ms |
9080 KB |
Output is correct |
16 |
Correct |
11 ms |
9080 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
11 ms |
9080 KB |
Output is correct |
2 |
Correct |
10 ms |
9080 KB |
Output is correct |
3 |
Correct |
11 ms |
9112 KB |
Output is correct |
4 |
Correct |
10 ms |
9080 KB |
Output is correct |
5 |
Correct |
10 ms |
9080 KB |
Output is correct |
6 |
Correct |
10 ms |
9080 KB |
Output is correct |
7 |
Correct |
12 ms |
9080 KB |
Output is correct |
8 |
Correct |
11 ms |
9080 KB |
Output is correct |
9 |
Correct |
11 ms |
9080 KB |
Output is correct |
10 |
Correct |
11 ms |
9080 KB |
Output is correct |
11 |
Correct |
11 ms |
9080 KB |
Output is correct |
12 |
Correct |
10 ms |
9080 KB |
Output is correct |
13 |
Correct |
11 ms |
9080 KB |
Output is correct |
14 |
Correct |
10 ms |
9080 KB |
Output is correct |
15 |
Correct |
11 ms |
9080 KB |
Output is correct |
16 |
Correct |
11 ms |
9080 KB |
Output is correct |
17 |
Correct |
12 ms |
9208 KB |
Output is correct |
18 |
Correct |
12 ms |
9336 KB |
Output is correct |
19 |
Correct |
12 ms |
9336 KB |
Output is correct |
20 |
Correct |
11 ms |
9080 KB |
Output is correct |
21 |
Correct |
12 ms |
9080 KB |
Output is correct |
22 |
Correct |
12 ms |
9208 KB |
Output is correct |
23 |
Correct |
12 ms |
9336 KB |
Output is correct |
24 |
Correct |
12 ms |
9336 KB |
Output is correct |
25 |
Correct |
12 ms |
9208 KB |
Output is correct |
26 |
Correct |
11 ms |
9208 KB |
Output is correct |
27 |
Correct |
12 ms |
9208 KB |
Output is correct |
28 |
Correct |
12 ms |
9848 KB |
Output is correct |
29 |
Correct |
13 ms |
10104 KB |
Output is correct |
30 |
Correct |
12 ms |
9080 KB |
Output is correct |
31 |
Correct |
11 ms |
9212 KB |
Output is correct |
32 |
Correct |
11 ms |
9080 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
11 ms |
9080 KB |
Output is correct |
2 |
Correct |
10 ms |
9080 KB |
Output is correct |
3 |
Correct |
11 ms |
9112 KB |
Output is correct |
4 |
Correct |
10 ms |
9080 KB |
Output is correct |
5 |
Correct |
10 ms |
9080 KB |
Output is correct |
6 |
Correct |
10 ms |
9080 KB |
Output is correct |
7 |
Correct |
12 ms |
9080 KB |
Output is correct |
8 |
Correct |
11 ms |
9080 KB |
Output is correct |
9 |
Correct |
11 ms |
9080 KB |
Output is correct |
10 |
Correct |
11 ms |
9080 KB |
Output is correct |
11 |
Correct |
11 ms |
9080 KB |
Output is correct |
12 |
Correct |
10 ms |
9080 KB |
Output is correct |
13 |
Correct |
11 ms |
9080 KB |
Output is correct |
14 |
Correct |
10 ms |
9080 KB |
Output is correct |
15 |
Correct |
11 ms |
9080 KB |
Output is correct |
16 |
Correct |
11 ms |
9080 KB |
Output is correct |
17 |
Correct |
12 ms |
9208 KB |
Output is correct |
18 |
Correct |
12 ms |
9336 KB |
Output is correct |
19 |
Correct |
12 ms |
9336 KB |
Output is correct |
20 |
Correct |
11 ms |
9080 KB |
Output is correct |
21 |
Correct |
12 ms |
9080 KB |
Output is correct |
22 |
Correct |
12 ms |
9208 KB |
Output is correct |
23 |
Correct |
12 ms |
9336 KB |
Output is correct |
24 |
Correct |
12 ms |
9336 KB |
Output is correct |
25 |
Correct |
12 ms |
9208 KB |
Output is correct |
26 |
Correct |
11 ms |
9208 KB |
Output is correct |
27 |
Correct |
12 ms |
9208 KB |
Output is correct |
28 |
Correct |
12 ms |
9848 KB |
Output is correct |
29 |
Correct |
13 ms |
10104 KB |
Output is correct |
30 |
Correct |
12 ms |
9080 KB |
Output is correct |
31 |
Correct |
11 ms |
9212 KB |
Output is correct |
32 |
Correct |
11 ms |
9080 KB |
Output is correct |
33 |
Correct |
174 ms |
23148 KB |
Output is correct |
34 |
Correct |
115 ms |
25256 KB |
Output is correct |
35 |
Correct |
149 ms |
19316 KB |
Output is correct |
36 |
Correct |
295 ms |
33216 KB |
Output is correct |
37 |
Correct |
41 ms |
16760 KB |
Output is correct |
38 |
Correct |
334 ms |
35816 KB |
Output is correct |
39 |
Correct |
357 ms |
35928 KB |
Output is correct |
40 |
Correct |
348 ms |
35916 KB |
Output is correct |
41 |
Correct |
342 ms |
35888 KB |
Output is correct |
42 |
Correct |
310 ms |
36072 KB |
Output is correct |
43 |
Correct |
334 ms |
35816 KB |
Output is correct |
44 |
Correct |
350 ms |
35992 KB |
Output is correct |
45 |
Correct |
341 ms |
36072 KB |
Output is correct |
46 |
Correct |
328 ms |
35940 KB |
Output is correct |
47 |
Correct |
322 ms |
35944 KB |
Output is correct |
48 |
Correct |
125 ms |
28344 KB |
Output is correct |
49 |
Correct |
149 ms |
33304 KB |
Output is correct |
50 |
Correct |
44 ms |
14192 KB |
Output is correct |
51 |
Correct |
59 ms |
18516 KB |
Output is correct |
52 |
Correct |
32 ms |
13936 KB |
Output is correct |
53 |
Correct |
205 ms |
34028 KB |
Output is correct |
54 |
Correct |
113 ms |
20144 KB |
Output is correct |
55 |
Correct |
262 ms |
27948 KB |
Output is correct |
56 |
Correct |
143 ms |
21408 KB |
Output is correct |
57 |
Correct |
222 ms |
32312 KB |
Output is correct |
58 |
Correct |
48 ms |
19492 KB |
Output is correct |
59 |
Correct |
57 ms |
17648 KB |
Output is correct |
60 |
Correct |
131 ms |
30452 KB |
Output is correct |
61 |
Correct |
143 ms |
31448 KB |
Output is correct |
62 |
Correct |
101 ms |
26952 KB |
Output is correct |
63 |
Correct |
98 ms |
58620 KB |
Output is correct |
64 |
Correct |
279 ms |
78560 KB |
Output is correct |
65 |
Correct |
172 ms |
112760 KB |
Output is correct |
66 |
Correct |
88 ms |
28280 KB |
Output is correct |
67 |
Correct |
135 ms |
81784 KB |
Output is correct |
68 |
Correct |
229 ms |
105976 KB |
Output is correct |
69 |
Correct |
48 ms |
17144 KB |
Output is correct |
70 |
Correct |
18 ms |
9976 KB |
Output is correct |
71 |
Correct |
106 ms |
61048 KB |
Output is correct |
72 |
Correct |
197 ms |
106360 KB |
Output is correct |
73 |
Correct |
1198 ms |
146040 KB |
Output is correct |
74 |
Correct |
308 ms |
94584 KB |
Output is correct |
75 |
Correct |
412 ms |
145144 KB |
Output is correct |
76 |
Correct |
248 ms |
126456 KB |
Output is correct |
77 |
Correct |
282 ms |
99680 KB |
Output is correct |