#include "catdog.h"
#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
using namespace std;
#define X first
#define Y second
#define pb push_back
typedef pair<int, int> ii;
typedef long long ll;
const int maxn = 1e5+5;
int n;
vector<int> adj[maxn];
int par[22][maxn];
int dep[maxn];
int cnt[maxn];
int prf[maxn];
int pos[maxn];
int head[maxn];
int stat[maxn]; //1 cat 2 Dog
int run = 0;
struct segtree
{
ll st[4*maxn];
ll lz[4*maxn];
void push(int p, int L, int R)
{
if(!lz) return;
st[p] += lz[p];
if(L != R)
{
lz[2*p] += lz[p];
lz[2*p+1] += lz[p];
}
lz[p] = 0;
}
void pull(int p)
{
st[p] = st[2*p] + st[2*p+1];
}
void update(int i, int j, int dx, int p = 1, int L = 1, int R = n)
{
push(p, L, R);
if(i> R || j< L) return;
if(i<= L && R<= j)
{
lz[p] += dx;
push(p, L, R);
return;
}
int M = (L+R)/2;
update(i, j, dx, 2*p, L, M);
update(i, j, dx, 2*p+1, M+1, R);
pull(p);
}
int ask(int i, int j, int p = 1, int L = 1, int R = n)
{
if(i> R || j< L) return 0;
push(p, L, R);
if(i<= L && R<= j) return st[p];
int M = (L+R)/2;
int x = ask(i, j, 2*p, L, M);
int y = ask(i, j, 2*p+1, M+1, R);
return x+y;
}
};
segtree Cat, Dog, sum;
void changeme(segtree &st, int u, int v, int dx)
{
if(dep[u]< dep[v]) return;
while(head[u] != head[v])
{
st.update(pos[head[u]], pos[u], dx);
u = par[0][head[u]];
}
st.update(pos[v], pos[u], dx);
}
int gimme(segtree &st, int u, int v)
{
//v higher than u, v an ancestor of u
if(v == 0) v = 1;
int res = 0;
while(head[u] != head[v])
{
res += st.ask(pos[head[u]], pos[u]);
u = par[0][head[u]];
}
res += st.ask(pos[v], pos[u]);
return res;
}
void dfs(int u = 1, int p = 0)
{
dep[u] = dep[p]+1;
par[0][u] = p;
for(int i = 1; i<= 20; i++) par[i][u] = par[i-1][par[i-1][u]];
cnt[u] = 1;
ii big = {0, -1};
for(int v : adj[u])
{
if(v == p) continue;
dfs(v, u);
big = max(big, {cnt[v], v});
cnt[u] += cnt[v];
}
prf[u] = big.Y;
}
void hld()
{
for(int i = 1; i<= n; i++)
{
if(prf[par[0][i]] == i) continue;
for(int j = i; j != -1; j = prf[j])
{
head[j] = i;
pos[j] = ++run;
}
}
}
void initialize(int N, vector<int> A, vector<int> B)
{
n = N;
for(int i = 0; i< n-1; i++)
{
adj[A[i]].pb(B[i]);
adj[B[i]].pb(A[i]);
}
dfs(); hld();
// printf("ok\n");
}
int cat(int u)
{
int c = gimme(Cat, u, u);
int d = gimme(Dog, u, u);
int cc = min(c, d+1);
int dd = min(d, c+1);
int cx = c;
int dx = c+1;
int cur = u;
for(int i = 20; i>= 0; i--)
{
if(gimme(sum, u, par[i][cur]) == 0)
{
cur = par[i][cur];
}
}
// printf("cur = %d\n", cur);
cur = par[0][cur];
bool iszero = (cur == 0);
if(cur == 0) cur = 1;
changeme(Cat, par[0][u], cur, cx-cc);
changeme(Dog, par[0][u], cur, dx-dd);
if(!iszero)
{
int st = stat[cur];
if(st == 1)
{
dd = cc+1;
dx = cx+1;
}
else
{
cc = dd+1;
cx = dx+1;
}
cur = par[0][cur];
if(cur)
{
changeme(Cat, cur, 1, cx-cc);
changeme(Dog, cur, 1, dx-dd);
}
}
stat[u] = 1;
// for(int i = 1; i<= n; i++) printf("%d ", gimme(Cat, i, i));
// printf("\n");
// for(int i = 1; i<= n; i++) printf("%d ", gimme(Dog, i, i));
// printf("\n");
if(stat[u] == 1) return gimme(Cat, 1, 1);
if(stat[u] == 2) return gimme(Dog, 1, 1);
return min(gimme(Cat, 1, 1), gimme(Dog, 1, 1));
}
int dog(int u)
{
int c = gimme(Cat, u, u);
int d = gimme(Dog, u, u);
int cc = min(c, d+1);
int dd = min(d, c+1);
int cx = d+1;
int dx = d;
int cur = u;
for(int i = 20; i>= 0; i--)
{
if(gimme(sum, u, par[i][cur]) == 0)
{
cur = par[i][cur];
}
}
cur = par[0][cur];
bool iszero = (cur == 0);
if(cur == 0) cur = 1;
changeme(Cat, par[0][u], cur, cx-cc);
changeme(Dog, par[0][u], cur, dx-dd);
if(!iszero)
{
int st = stat[cur];
if(st == 1)
{
dd = cc+1;
dx = cx+1;
}
else
{
cc = dd+1;
cx = dx+1;
}
cur = par[0][cur];
if(cur)
{
changeme(Cat, cur, 1, cx-cc);
changeme(Dog, cur, 1, dx-dd);
}
}
stat[u] = 2;
// for(int i = 1; i<= n; i++) printf("%d ", gimme(Cat, i, i));
// printf("\n");
// for(int i = 1; i<= n; i++) printf("%d ", gimme(Dog, i, i));
// printf("\n");
if(stat[u] == 1) return gimme(Cat, 1, 1);
if(stat[u] == 2) return gimme(Dog, 1, 1);
return min(gimme(Cat, 1, 1), gimme(Dog, 1, 1));
}
int neighbor(int u)
{
int c = gimme(Cat, u, u);
int d = gimme(Dog, u, u);
int cc, dd;
if(stat[u] == 1)
{
cc = c;
dd = c+1;
}
else
{
cc = d+1;
dd = d;
}
int cx = min(c, d+1);
int dx = min(c+1, d);
int cur = u;
for(int i = 20; i>= 0; i--)
{
if(gimme(sum, u, par[i][cur]) == 0)
{
cur = par[i][cur];
}
}
cur = par[0][cur];
bool iszero = (cur == 0);
if(cur == 0) cur = 1;
changeme(Cat, par[0][u], cur, cx-cc);
changeme(Dog, par[0][u], cur, dx-dd);
if(!iszero)
{
int st = stat[cur];
if(st == 1)
{
dd = cc+1;
dx = cx+1;
}
else
{
cc = dd+1;
cx = dx+1;
}
cur = par[0][cur];
if(cur)
{
changeme(Cat, cur, 1, cx-cc);
changeme(Dog, cur, 1, dx-dd);
}
}
stat[u] = 0;
// for(int i = 1; i<= n; i++) printf("%d ", gimme(Cat, i, i));
// printf("\n");
// for(int i = 1; i<= n; i++) printf("%d ", gimme(Dog, i, i));
// printf("\n");
if(stat[u] == 1) return gimme(Cat, 1, 1);
if(stat[u] == 2) return gimme(Dog, 1, 1);
return min(gimme(Cat, 1, 1), gimme(Dog, 1, 1));
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
2816 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
2816 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
2816 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
