Submission #153767

#	Time	Username	Problem	Language	Result	Execution time	Memory
153767		tutis	Cats or Dogs (JOI18_catdog)	C++17	100 / 100	1642 ms	27256 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;
for(int t=0;t<adj[i].size();t++)
{
int j=adj[i][t];
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>
  ^~~~~~
catdog.cpp: In function 'void hld(int, int, int)':
catdog.cpp:30:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 for(int t=0;t<adj[i].size();t++)
             ~^~~~~~~~~~~~~~

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