Submission #153772

#	Time	Username	Problem	Language	Result	Execution time	Memory
153772		tutis	Cats or Dogs (JOI18_catdog)	C++17	100 / 100	1626 ms	26616 KiB

catdog

#import<bits/stdc++.h>
using namespace std;const int N=101010;vector<int>adj[N];int pa[N];int dfs(int i,int p){pa[i]=p;int sz=1;pair<int,int>mx={0,0};for(int t=0;t<(int)adj[i].size();t++){int j=adj[i][t];if(j==p)continue;int x=dfs(j,i);sz+=x;mx=max(mx,{x,t});}swap(adj[i][0],adj[i][mx.second]);return sz;}int timer=1;int nr[N],head[N],tail[N];void hld(int i,int p,int h){nr[i]=timer++;head[i]=h;tail[h]=i;int t=0;for(int j:adj[i]){if(j!=p)hld(j,i,t++==0?h:j);}}struct line{int cc=0,cd=N,dd=0,dc=N;int mn(int c){if(c)return min({cd,cc,dc+1,dd+1});else return min({cd+1,cc+1,dc,dd});}};line merge(line a,line b){line c;c.cc=min({a.cc+b.cc,a.cc+b.dc+1,a.cd+b.cc+1,a.cd+b.dc});c.cd=min({a.cc+b.cd,a.cc+b.dd+1,a.cd+b.cd+1,a.cd+b.dd});c.dd=min({a.dc+b.cd,a.dc+b.dd+1,a.dd+b.cd+1,a.dd+b.dd});c.dc=min({a.dc+b.cc,a.dc+b.dc+1,a.dd+b.cc+1,a.dd+b.dc});return c;}struct ST{line X;int l,r;ST*left,*right;ST(int l,int r):l(l),r(r){if(l<r){left=new ST(l,(l+r)/2);right=new ST((l+r)/2+1,r);X=merge(left->X,right->X);}}line get(int x,int y){if(x<=l&&r<=y)return X;if(r<x||y<l)return line();return merge(left->get(x,y),right->get(x,y));}void set(int x,int w,int c){if(l==r){if(c)X.cc=w;else X.dd=w;}else{if(x<=(l+r)/2)left->set(x,w,c);else right->set(x,w,c);X=merge(left->X,right->X);}}}medis(0,N);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]);}dfs(1,0);hld(1,0,1);}int C[N],D[N],V[N];int fix(int v,int p){V[v]=p;while(true){int w=head[v];line X=medis.get(nr[w],nr[tail[w]]);C[pa[w]]-=X.mn(1);D[pa[w]]-=X.mn(0);medis.set(nr[v],V[v]==1?N:C[v],1);medis.set(nr[v],V[v]==2?N:D[v],0);X=medis.get(nr[w],nr[tail[w]]);C[pa[w]]+=X.mn(1);D[pa[w]]+=X.mn(0);if(v==1)break;if(v!=w)v=w;else v=pa[v];}return min(C[0],D[0]);}int cat(int v){return fix(v,2);}int dog(int v){return fix(v,1);}int neighbor(int v){return fix(v,0);}

Compilation message (stderr)

catdog.cpp:1:2: warning: #import is a deprecated GCC extension [-Wdeprecated]
 #import<bits/stdc++.h>
  ^~~~~~

• Subtask 1: 8 / 8
• Subtask 2: 30 / 30
• Subtask 3: 62 / 62