#include "catdog.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 1e5;
const int INF = 1e6;
int N;
vector<int> adj[MAXN+10];
int sz[MAXN+10], par[MAXN+10], dep[MAXN+10];
int idx[MAXN+10], cnt=1, head[MAXN+10], tail[MAXN+10];
int A[MAXN+10], C[MAXN+10], D[MAXN+10];
struct Node
{
int AA, AB, BA, BB;
Node(int AA, int AB, int BA, int BB) : AA(AA), AB(AB), BA(BA), BB(BB) {}
Node() : AA(0), AB(0), BA(0), BB(0) {}
};
Node combine(Node lc, Node rc)
{
Node ret;
ret.AA=min({lc.AA+rc.AA, lc.AA+rc.BA+1, lc.AB+rc.AA+1, lc.AB+rc.BA});
ret.AB=min({lc.AA+rc.AB, lc.AA+rc.BB+1, lc.AB+rc.AB+1, lc.AB+rc.BB});
ret.BA=min({lc.BA+rc.AA, lc.BA+rc.BA+1, lc.BB+rc.AA+1, lc.BB+rc.BA});
ret.BB=min({lc.BA+rc.AB, lc.BA+rc.BB+1, lc.BB+rc.AB+1, lc.BB+rc.BB});
return ret;
}
struct SEG
{
Node tree[MAXN*4+10];
void init(int node, int tl, int tr)
{
if(tl==tr) { tree[node]=Node(0, INF, INF, 0); return; }
int mid=tl+tr>>1;
init(node*2, tl, mid);
init(node*2+1, mid+1, tr);
tree[node]=combine(tree[node*2], tree[node*2+1]);
}
void update(int node, int tl, int tr, int pos, Node val)
{
if(tr<pos || pos<tl) return;
if(tl==tr)
{
tree[node]=val;
return;
}
int mid=tl+tr>>1;
update(node*2, tl, mid, pos, val);
update(node*2+1, mid+1, tr, pos, val);
tree[node]=combine(tree[node*2], tree[node*2+1]);
}
void query(int node, int tl, int tr, int l, int r, vector<Node> &ret)
{
if(l<=tl && tr<=r) { ret.push_back(tree[node]); return; }
if(r<tl || tr<l) return;
int mid=tl+tr>>1;
query(node*2, tl, mid, l, r, ret);
query(node*2+1, mid+1, tr, l, r, ret);
}
Node query(int l, int r)
{
int i, j;
vector<Node> V;
query(1, 1, N, l, r, V);
Node ret=V[0];
for(i=1; i<V.size(); i++) ret=combine(ret, V[i]);
return ret;
}
void debug(int node, int tl, int tr)
{
printf("%d %d %d : %d %d %d %d\n", node, tl, tr, tree[node].AA, tree[node].AB, tree[node].BA, tree[node].BB);
if(tl==tr) return;
int mid=tl+tr>>1;
debug(node*2, tl, mid);
debug(node*2+1, mid+1, tr);
}
}seg;
void dfs(int now, int bef, int depth)
{
sz[now]=1;
par[now]=bef;
dep[now]=depth;
for(int nxt : adj[now])
{
if(nxt==bef) continue;
dfs(nxt, now, depth+1);
sz[now]+=sz[nxt];
}
}
void hld(int now, int bef)
{
idx[now]=cnt++;
int heavy=0;
for(int nxt : adj[now])
{
if(nxt==bef) continue;
if(sz[heavy]<sz[nxt]) heavy=nxt;
}
if(heavy==0)
{
tail[now]=now;
return;
}
head[heavy]=head[now];
hld(heavy, now);
for(int nxt : adj[now])
{
if(nxt==bef || nxt==heavy) continue;
head[nxt]=nxt;
hld(nxt, now);
}
tail[now]=tail[heavy];
}
void initialize(int _N, vector<int> A, vector<int> B)
{
int i, j;
N=_N;
for(i=0; i<N-1; i++)
{
adj[A[i]].push_back(B[i]);
adj[B[i]].push_back(A[i]);
}
dfs(1, 0, 1);
head[1]=1;
hld(1, 0);
seg.init(1, 1, N);
}
int query(int u, int val)
{
Node chg;
if(val==0) chg=Node(C[u], INF, INF, D[u]);
if(val==1)
{
Node t=seg.query(idx[u], idx[u]);
D[u]=t.BB;
chg=Node(C[u], INF, INF, INF);
}
if(val==2)
{
Node t=seg.query(idx[u], idx[u]);
C[u]=t.AA;
chg=Node(INF, INF, INF, D[u]);
}
A[u]=val;
while(head[u]!=1)
{
int a=par[head[u]], b=head[u];
Node qa=seg.query(idx[a], idx[a]), qb=seg.query(idx[head[b]], idx[tail[b]]);
if(A[a]!=2) qa.AA-=min(min(qb.AA, qb.AB), min(qb.BA, qb.BB)+1), C[a]-=min(min(qb.AA, qb.AB), min(qb.BA, qb.BB)+1);
if(A[a]!=1) qa.BB-=min(min(qb.AA, qb.AB)+1, min(qb.BA, qb.BB)), D[a]-=min(min(qb.AA, qb.AB)+1, min(qb.BA, qb.BB));
seg.update(1, 1, N, idx[u], chg);
qb=seg.query(idx[head[b]], idx[tail[b]]);
if(A[a]!=2) qa.AA+=min(min(qb.AA, qb.AB), min(qb.BA, qb.BB)+1), C[a]+=min(min(qb.AA, qb.AB), min(qb.BA, qb.BB)+1);
if(A[a]!=1) qa.BB+=min(min(qb.AA, qb.AB)+1, min(qb.BA, qb.BB)), D[a]+=min(min(qb.AA, qb.AB)+1, min(qb.BA, qb.BB));
chg=qa;
u=par[head[u]];
}
seg.update(1, 1, N, idx[u], chg);
Node ans=seg.query(idx[head[1]], idx[tail[1]]);
//seg.debug(1, 1, N); printf("===========================\n");
return min({ans.AA, ans.AB, ans.BA, ans.BB});
}
int cat(int u)
{
return query(u, 1);
}
int dog(int u)
{
return query(u, 2);
}
int neighbor(int u)
{
return query(u, 0);
}
Compilation message
catdog.cpp: In member function 'void SEG::init(int, int, int)':
catdog.cpp:43:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid=tl+tr>>1;
~~^~~
catdog.cpp: In member function 'void SEG::update(int, int, int, int, Node)':
catdog.cpp:57:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid=tl+tr>>1;
~~^~~
catdog.cpp: In member function 'void SEG::query(int, int, int, int, int, std::vector<Node>&)':
catdog.cpp:67:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid=tl+tr>>1;
~~^~~
catdog.cpp: In member function 'Node SEG::query(int, int)':
catdog.cpp:78:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(i=1; i<V.size(); i++) ret=combine(ret, V[i]);
~^~~~~~~~~
catdog.cpp:74:16: warning: unused variable 'j' [-Wunused-variable]
int i, j;
^
catdog.cpp: In member function 'void SEG::debug(int, int, int)':
catdog.cpp:86:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid=tl+tr>>1;
~~^~~
catdog.cpp: In function 'void initialize(int, std::vector<int>, std::vector<int>)':
catdog.cpp:137:12: warning: unused variable 'j' [-Wunused-variable]
int i, j;
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
8952 KB |
Output is correct |
| 2 |
Correct |
10 ms |
8956 KB |
Output is correct |
| 3 |
Incorrect |
10 ms |
9000 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
8952 KB |
Output is correct |
| 2 |
Correct |
10 ms |
8956 KB |
Output is correct |
| 3 |
Incorrect |
10 ms |
9000 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
8952 KB |
Output is correct |
| 2 |
Correct |
10 ms |
8956 KB |
Output is correct |
| 3 |
Incorrect |
10 ms |
9000 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
