Submission #1096062

#TimeUsernameProblemLanguageResultExecution timeMemory
1096062AntaresMousetrap (CEOI17_mousetrap)C++14
25 / 100
913 ms64340 KiB
#include <iostream> #include <vector> #include <bitset> #include <algorithm> #define inf 2000000 using namespace std; vector <int> v[1000001]; bitset <1000001> vis; int n,m,t,k,nr; int val_noduri[1000001],fr[1000001],noduri[1000001],vecini[1000001],last_vecini[1000001],p[1000001],dp[1000001]; struct pozitie { int val,pos,lazy; } sol; struct seg_tree { pozitie aint[4000001]; void f (int nod,bool ok) { if ((ok&&aint[2*nod].val>=aint[2*nod+1].val)||(!ok&&aint[2*nod].val<=aint[2*nod+1].val)) aint[nod]=aint[2*nod]; else aint[nod]=aint[2*nod+1]; aint[nod].lazy=0; } void build (int nod,int st,int dr,int v[],bool ok) { aint[nod].lazy=0; if (st==dr) { aint[nod].val=v[st]; aint[nod].pos=st; } else { int mij=(st+dr)/2; build (2*nod,st,mij,v,ok); build (2*nod+1,mij+1,dr,v,ok); f (nod,ok); } } void propagate (int nod,int st,int dr) { if (st!=dr) { aint[2*nod].val+=aint[nod].lazy; aint[2*nod+1].val+=aint[nod].lazy; aint[2*nod].lazy+=aint[nod].lazy; aint[2*nod+1].lazy+=aint[nod].lazy; } aint[nod].lazy=0; } void update (int nod,int st,int dr,int a,int b,int x,bool ok) { if (a>b) return ; propagate (nod,st,dr); if (st>=a&&dr<=b) { aint[nod].val+=x; aint[nod].lazy+=x; } else { int mij=(st+dr)/2; if (a<=mij) update (2*nod,st,mij,a,b,x,ok); if (b>mij) update (2*nod+1,mij+1,dr,a,b,x,ok); f (nod,ok); } } pozitie query () { return aint[1]; } }; seg_tree aint_noduri,aint_vecini; void dfs (int nod,int t) { p[nod]=t; for (int i=0; i<v[nod].size (); i++) { int vecin=v[nod][i]; if (vecin!=t) dfs (vecin,nod); } } void dfs_dp (int nod,int t) { int max1=0,max2=0,nr=0; for (int i=0; i<v[nod].size (); i++) { int vecin=v[nod][i]; if (vecin==t) continue; nr++; dfs_dp (vecin,nod); if (dp[vecin]>=max1) { max2=max1; max1=dp[vecin]; } else if (dp[vecin]>max2) max2=dp[vecin]; } dp[nod]=max2+nr; } void read () { cin>>n>>t>>m; int x,y; for (int i=1; i<n; i++) { cin>>x>>y; v[x].push_back (y); v[y].push_back (x); } } void get_nodes () { int pos=m; k=0; while (pos!=t) { k++; noduri[k]=pos; val_noduri[k]=k; vis[pos]=1; pos=p[pos]; } vis[t]=1; reverse (noduri+1,noduri+k+1); reverse (val_noduri+1,val_noduri+k+1); aint_noduri.build (1,1,k,val_noduri,0); } void get_vecini () { int nrant; nr=0; for (int i=1; i<=k; i++) { nrant=nr; for (int j=0; j<v[noduri[i]].size (); j++) { int vecin=v[noduri[i]][j]; if (!vis[vecin]) { dfs_dp (vecin,noduri[i]); vecini[++nr]=dp[vecin]; fr[nr]=i; } } for (int j=nrant+1; j<=nr; j++) vecini[j]+=nr; last_vecini[i]=nr; } aint_vecini.build (1,1,nr,vecini,1); } void solve () { if (nr==0) { cout<<0; exit (0); } int nrvec=min (nr,k),minim=1,maxim=0,pos,nrc=0; while (nrvec>=0&&minim>=0) { sol=aint_vecini.query (); maxim=sol.val; pos=sol.pos; if (maxim<=nrc) { maxim=nrc; break; } aint_noduri.update (1,1,k,1,fr[pos],-1,0); sol=aint_noduri.query (); minim=sol.val; if (minim<0) break; nrvec--; nrc++; aint_vecini.update (1,1,nr,pos,pos,-inf,1); aint_vecini.update (1,1,nr,1,last_vecini[fr[pos]-1],1,1); } cout<<maxim; } int main () { read (); dfs (t,0); get_nodes (); get_vecini (); solve (); return 0; }

Compilation message (stderr)

mousetrap.cpp: In function 'void dfs(int, int)':
mousetrap.cpp:82:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |     for (int i=0; i<v[nod].size (); i++)
      |                   ~^~~~~~~~~~~~~~~
mousetrap.cpp: In function 'void dfs_dp(int, int)':
mousetrap.cpp:92:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |     for (int i=0; i<v[nod].size (); i++)
      |                   ~^~~~~~~~~~~~~~~
mousetrap.cpp: In function 'void get_vecini()':
mousetrap.cpp:144:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  144 |         for (int j=0; j<v[noduri[i]].size (); j++)
      |                       ~^~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...