Submission #964160

#TimeUsernameProblemLanguageResultExecution timeMemory
964160Trisanu_DasCats or Dogs (JOI18_catdog)C++17
100 / 100
151 ms23268 KiB
#include "catdog.h" #include <stdio.h> #include <vector> #include <algorithm> using namespace std; #define mp make_pair #define pb push_back const int inf=1e9+7; int min(int a, int b){ return a>b?b:a;} const int N=100050; const int M=2*N; struct Matrix { int a[2][2]; void init(){ a[0][0]=a[1][1]=0;a[1][0]=a[0][1]=inf;} Matrix(){ init();} Matrix operator * (Matrix b) const { Matrix c; int i,j,k,l; for(i=0;i<2;i++) for(j=0;j<2;j++) { c.a[i][j]=inf; for(k=0;k<2;k++) for(l=0;l<2;l++) c.a[i][j]=min(c.a[i][j],a[i][k]+b.a[l][j]+(k^l)); } return c; } } node[M]; int ls[M],rs[M],root[N],tsz; void Set(int &c, int ss, int se, int qi, int a, int b) { if(!c) c=++tsz; if(ss==se){ node[c].a[0][0]+=a;node[c].a[1][1]+=b;return;} int mid=ss+se>>1; if(qi<=mid) Set(ls[c],ss,mid,qi,a,b); else Set(rs[c],mid+1,se,qi,a,b); node[c]=node[ls[c]]*node[rs[c]]; } pair<int,int> Get(int c) { int a=min(node[c].a[0][0],node[c].a[0][1]); int b=min(node[c].a[1][0],node[c].a[1][1]); a=min(a,b+1); b=min(b,a+1); return mp(a,b); } int head[N],sz[N],dep[N],par[N],csz[N]; vector<int> E[N]; void DFS(int u, int p) { par[u]=p;dep[u]=dep[p]+1;sz[u]=1; for(int i=0;i<E[u].size();i++) if(E[u][i]!=p) DFS(E[u][i],u),sz[u]+=sz[E[u][i]]; } void HLD(int u, int p) { if(!head[u]) head[u]=u; csz[head[u]]++; int HC=0,i; for(i=0;i<E[u].size();i++) if(E[u][i]!=p && sz[HC]<sz[E[u][i]]) HC=E[u][i]; if(HC) head[HC]=head[u]; for(i=0;i<E[u].size();i++) if(E[u][i]!=p) HLD(E[u][i],u); } int t[N]; void initialize(int n, vector<int> a, vector<int> b) { for(int i=0;i<n-1;i++) E[a[i]].pb(b[i]),E[b[i]].pb(a[i]); DFS(1,0);HLD(1,0); } int Solve(){ pair<int,int> sol=Get(root[1]);return min(sol.first,sol.second);} void Set(int u, int a, int b) { while(u) { int la,lb,na,nb; pair<int,int> tmp=Get(root[head[u]]); la=tmp.first;lb=tmp.second; Set(root[head[u]],1,csz[head[u]],dep[u]-dep[head[u]]+1,a,b); tmp=Get(root[head[u]]); na=tmp.first;nb=tmp.second; a=na-la;b=nb-lb; u=par[head[u]]; } } int cat(int u){ t[u]=1;Set(u,N,0);return Solve();} int dog(int u){ t[u]=2;Set(u,0,N);return Solve();} int neighbor(int u) { if(t[u]==1) Set(u,-N,0); if(t[u]==2) Set(u,0,-N); return Solve(); }

Compilation message (stderr)

catdog.cpp: In function 'void Set(int&, int, int, int, int, int)':
catdog.cpp:34:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   34 |  int mid=ss+se>>1;
      |          ~~^~~
catdog.cpp: In function 'void DFS(int, int)':
catdog.cpp:52:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |  for(int i=0;i<E[u].size();i++) if(E[u][i]!=p) DFS(E[u][i],u),sz[u]+=sz[E[u][i]];
      |              ~^~~~~~~~~~~~
catdog.cpp: In function 'void HLD(int, int)':
catdog.cpp:59:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |  for(i=0;i<E[u].size();i++) if(E[u][i]!=p && sz[HC]<sz[E[u][i]]) HC=E[u][i];
      |          ~^~~~~~~~~~~~
catdog.cpp:61:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |  for(i=0;i<E[u].size();i++) if(E[u][i]!=p) HLD(E[u][i],u);
      |          ~^~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...