| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 118077 | kig9981 | Cats or Dogs (JOI18_catdog) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#include "catdog.h"
const int SZ=1<<17;
vector<int> adj[100000];
int node_cnt, depth[100000], parent[100000], W[100000], num[100000], num_rev[100000], hld[100000], V[100000], ans;
pair<int,int> tree[2*SZ], itree[2*SZ];
void set_tree(int n, int v)
{
for(itree[n+=SZ].first=v;n>>=1;) itree[n]=max(itree[2*n],itree[2*n+1]);
}
pair<int,int> get_max(int s, int e)
{
pair<int,int> ret;
for(s+=SZ,e+=SZ;s<=e;s>>=1,e>>=1) {
if(s&1) ret=max(ret,itree[s++]);
if(~e&1) ret=max(ret,itree[e--]);
}
return ret;
}
void add_tree(int s, int e, int v1, int v2)
{
for(s+=SZ,e+=SZ;s<=e;s>>=1,e>>=1) {
if(s&1) {
tree[s].first+=v1;
tree[s++].second+=v2;
}
if(~e&1) {
tree[e].first+=v1;
tree[e--].second+=v2;
}
}
}
pair<int,int> get_value(int n)
{
pair<int,int> ret;
for(ret=tree[n+=SZ];n>>=1;) {
ret.first+=tree[n].first;
ret.second+=tree[n].second;
}
return ret;
}
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];
}
void dfs2(int c)
{
num[c]=node_cnt++;
num_rev[num[c]]=c;
for(auto n: adj[c]) if(parent[n]==c && 2*W[n]>=W[c]) {
hld[n]=hld[c];
dfs2(n);
}
for(auto n: adj[c]) if(parent[n]==c && 2*W[n]<W[c]) {
hld[n]=n;
dfs2(n);
}
}
void initialize(int N, vector<int> A, vector<int> B)
{
itree[N-1].second=N-1; parent[0]=-1;
for(int i=0;i<N-1;i++) {
adj[--A[i]].push_back(--B[i]);
adj[B[i]].push_back(A[i]);
itree[i].second=i;
}
dfs(0); dfs2(0);
for(int i=SZ-1;i;i--) itree[i]=max(itree[2*i],itree[2*i+1]);
}
int query(int a)
{
while(a>=0) {
auto temp=get_max(num[hld[a]],num[a]);
if(temp.first) {
int s=hld[a], e=a;
while(s<=e) {
int m=(s+e)>>1;
temp=get_max(num[m],num[a]);
if(temp.first) s=m+1;
else e=m-1;
}
return temp.second;
}
a=parent[hld[a]];
}
return 0;
}
void update(int a, int b, int v1, int v2)
{
if(b==-1) return;
while(hld[a]!=hld[b]) {
add_tree(num[hld[b]],num[b],v1,v2);
b=parent[hld[b]];
}
add_tree(num[a],num[b],v1,v2);
}
int cat(int c)
{
int idx=num[--c], pidx=query(c);
auto[v1,v2]=get_value(idx);
auto[pv1,pv2]=get_value(pidx);
if(pidx || V[pidx]) {
if(V[pidx]==1) ans-=pv2;
else if(V[pidx]==2) ans-=pv1-1;
}
else ans+=min(pv1+1-v1,pv2-v2)-min(pv1,pv2);
V[idx]=1; set_tree(idx,1);
ans+=v2;
update(num_rev[pidx],parent[num_rev[idx]],1-v1,-v2);
return ans;
}
int dog(int c)
{
int idx=num[--c], pidx=query(c);
auto[v1,v2]=get_value(idx);
auto[pv1,pv2]=get_value(pidx);
if(pidx || V[pidx]) {
if(V[pidx]==1) ans-=pv2-1;
else if(V[pidx]==2) ans-=pv1;
}
else ans+=min(pv1-v1,pv2+1-v2)-min(pv1,pv2);
V[idx]=2; set_tree(idx,2);
ans+=v1;
update(num_rev[pidx],parent[num_rev[idx]],-v1,1-v2);
return ans;
}
int neighbor(int c)
{
int idx=num[--c], pidx=query(parent[c]);
auto[v1,v2]=get_value(idx);
auto[pv1,pv2]=get_value(pidx);
if(pidx || V[pidx]) {
if(V[pidx]==1) ans-=pv2-v2;
else if(V[pidx]==2) ans-=pv1-v1;
}
else ans+=min(pv1+v1-(V[idx]==1),pv2+v2-(V[idx]==2))-min(pv1,pv2);
if(V[idx]==1) ans-=v2;
else if(V[idx]==2) ans-=v1;
update(num_rev[pidx],parent[num_rev[idx]],v1-(V[idx]==1),v2-(V[idx]==2));
V[idx]=0; set_tree(idx,0);
return ans;
}