#include <bits/stdc++.h>
#include "catdog.h"
using namespace std;
const int SZ=1<<17;
vector<int> adj[100000];
int N, depth[100000], parent[100000], W[100000], num[100000], R[100000], hld[100000], V[100000], tree[2*SZ][4];
void add_tree(int n, int v1, int v2)
{
n+=SZ;
tree[n][0]+=v1; tree[n][3]+=v2;
while(n>>=1) {
for(int i=0;i<4;i++) tree[n][i]=0x1fffffff;
for(int i=0;i<4;i++) for(int j=0;j<4;j++) tree[n][(i&2)|(j&1)]=min(tree[n][(i&2)|(j&1)],tree[2*n][i]+tree[2*n+1][j]+((i&1)!=(j>>1)));
}
}
void get_ans(int *ret, int s, int e)
{
int r1[4]={0,0x1fffffff,0x1fffffff,0}, r2[4]={0,0x1fffffff,0x1fffffff,0};
for(s+=SZ,e+=SZ;s<=e;s>>=1,e>>=1) {
if(s&1) {
for(int i=0;i<4;i++) ret[i]=0x1fffffff;
for(int i=0;i<4;i++) for(int j=0;j<4;j++) ret[(i&2)|(j&1)]=min(ret[(i&2)|(j&1)],r1[i]+tree[s][j]+((i&1)!=(j>>1)));
for(int i=0;i<4;i++) r1[i]=ret[i];
s++;
}
if(~e&1) {
for(int i=0;i<4;i++) ret[i]=0x1fffffff;
for(int i=0;i<4;i++) for(int j=0;j<4;j++) ret[(i&2)|(j&1)]=min(ret[(i&2)|(j&1)],tree[e][i]+r2[j]+((i&1)!=(j>>1)));
for(int i=0;i<4;i++) r2[i]=ret[i];
e--;
}
}
for(int i=0;i<4;i++) ret[i]=0x1fffffff;
for(int i=0;i<4;i++) for(int j=0;j<4;j++) ret[(i&2)|(j&1)]=min(ret[(i&2)|(j&1)],r1[i]+r2[j]+((i&1)!=(j>>1)));
}
int dfs(int c)
{
W[c]=1;
for(auto n: adj[c]) if(W[n]==0) {
parent[n]=c;
depth[n]=depth[c]+1;
W[c]+=dfs(n);
}
return W[c];
}
int dfs2(int c)
{
num[c]=R[c]=N++;
for(auto n: adj[c]) if(parent[n]==c && 2*W[n]>=W[c]) {
hld[n]=hld[c];
R[c]=dfs2(n);
}
for(auto n: adj[c]) if(parent[n]==c && 2*W[n]<W[c]) {
hld[n]=n;
dfs2(n);
}
return R[c];
}
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]);
tree[SZ+i][1]=tree[SZ+i][2]=N;
}
tree[SZ+N-1][1]=tree[SZ+N-1][2]=N;
dfs(0); dfs2(0);
}
int cat(int c)
{
int t1[4], t2[4], v1=0, v2=N;
V[--c]=1;
for(;;) {
get_ans(t1,num[hld[c]],R[c]);
add_tree(num[c],v1,v2);
get_ans(t2,num[hld[c]],R[c]);
v1=min(t2[0],t2[1])-min(t1[0],t1[1]);
v2=min(t2[2],t2[3])-min(t1[2],t1[3]);
if(hld[c]==0) break;
c=parent[hld[c]];
}
return min({t2[0],t2[1],t2[2],t2[3]});
}
int dog(int c)
{
int t1[4], t2[4], v1=N, v2=0;
V[--c]=2;
for(;;) {
get_ans(t1,num[hld[c]],R[c]);
add_tree(num[c],v1,v2);
get_ans(t2,num[hld[c]],R[c]);
v1=min(t2[0],t2[1])-min(t1[0],t1[1]);
v2=min(t2[2],t2[3])-min(t1[2],t1[3]);
if(hld[c]==0) break;
c=parent[hld[c]];
}
return min({t2[0],t2[1],t2[2],t2[3]});
}
int neighbor(int c)
{
int t1[4], t2[4], v1=-N*(V[--c]==2), v2=-N*(V[c]==1);
V[c]=0;
for(;;) {
get_ans(t1,num[hld[c]],R[c]);
add_tree(num[c],v1,v2);
get_ans(t2,num[hld[c]],R[c]);
if(hld[c]==0) break;
v1=min(t2[0],t2[1])-min(t1[0],t1[1]);
v2=min(t2[2],t2[3])-min(t1[2],t1[3]);
c=parent[hld[c]];
}
return min({t2[0],t2[1],t2[2],t2[3]});
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
2688 KB |
Output is correct |
| 2 |
Correct |
3 ms |
2688 KB |
Output is correct |
| 3 |
Correct |
3 ms |
2688 KB |
Output is correct |
| 4 |
Correct |
4 ms |
2688 KB |
Output is correct |
| 5 |
Correct |
4 ms |
2816 KB |
Output is correct |
| 6 |
Incorrect |
4 ms |
2816 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
2688 KB |
Output is correct |
| 2 |
Correct |
3 ms |
2688 KB |
Output is correct |
| 3 |
Correct |
3 ms |
2688 KB |
Output is correct |
| 4 |
Correct |
4 ms |
2688 KB |
Output is correct |
| 5 |
Correct |
4 ms |
2816 KB |
Output is correct |
| 6 |
Incorrect |
4 ms |
2816 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
2688 KB |
Output is correct |
| 2 |
Correct |
3 ms |
2688 KB |
Output is correct |
| 3 |
Correct |
3 ms |
2688 KB |
Output is correct |
| 4 |
Correct |
4 ms |
2688 KB |
Output is correct |
| 5 |
Correct |
4 ms |
2816 KB |
Output is correct |
| 6 |
Incorrect |
4 ms |
2816 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
