Submission #64784

#TimeUsernameProblemLanguageResultExecution timeMemory
64784TadijaSebezTropical Garden (IOI11_garden)C++11
100 / 100
139 ms27320 KiB
#include "garden.h" #include "gardenlib.h" #include <stdio.h> #include <vector> #include <algorithm> using namespace std; #define pb push_back const int N=150050; const int M=2*N; //---------------------// /* void answer(int x){ printf("%i\n",x);} */ //---------------------// int go[M],deg[M],dep[M],cnt[M],sol[M]; vector<int> E[M]; pair<int,int> Qs[M]; void DFS(int u, int d) { dep[u]=d; for(int i=0;i<E[u].size();i++) { int v=E[u][i]; if(dep[v]==-1) DFS(v,d+1); } } bool was[M]; int Cycle(int u, int n) { int i,ret=0; for(i=0;i<n*2;i++) was[i]=0; for(i=u;!was[i];i=go[i]) was[i]=1,ret++; if(i==u) return ret; return 0; } void count_routes(int n, int m, int p, int r[][2], int q, int k[]) { int i,j,cyc; for(i=0;i<q;i++) Qs[i].first=k[i],Qs[i].second=i; sort(Qs,Qs+q); for(i=0;i<n*2;i++) go[i]=-1; for(i=0;i<m;i++) { int u=r[i][0],v=r[i][1]; int f1=0,f2=0; if(!~go[u<<1]) f1=1; else if(!~go[u<<1|1]) f1=2; if(!~go[v<<1]) f2=1; else if(!~go[v<<1|1]) f2=2; if(f1==1) go[u<<1]=f2==1?v<<1|1:v<<1; if(f1==2) go[u<<1|1]=f2==1?v<<1|1:v<<1; if(f2==1) go[v<<1]=f1==1?u<<1|1:u<<1; if(f2==2) go[v<<1|1]=f1==1?u<<1|1:u<<1; } for(i=0;i<n*2;i++) if(!~go[i]) go[i]=go[i^1]; for(i=0;i<n*2;i++) E[go[i]].pb(i);//,printf("%i -> %i\n",go[i],i); for(i=0;i<n*2;i++) dep[i]=-1; for(i=0;i<=n*2;i++) cnt[i]=0; DFS(p<<1,0); cyc=Cycle(p<<1,n); //printf("-> %i\n",cyc); if(!cyc) { for(i=0;i<n*2;i+=2) if(dep[i]>=0) cnt[dep[i]]++; for(i=0;i<q;i++) if(k[i]<=2*n) sol[i]+=cnt[k[i]]; } else { vector<int> Ds; for(i=0;i<n*2;i+=2) if(dep[i]>=0) Ds.pb(dep[i]); sort(Ds.begin(),Ds.end()); j=0; for(i=0;i<q;i++) { while(j<Ds.size() && Ds[j]<=Qs[i].first) cnt[Ds[j]%cyc]++,j++; sol[Qs[i].second]+=cnt[Qs[i].first%cyc]; } } //for(i=0;i<q;i++) printf("%i ",sol[i]);printf("\n"); for(i=0;i<n*2;i++) dep[i]=-1; for(i=0;i<=n*2;i++) cnt[i]=0; DFS(p<<1|1,0); cyc=Cycle(p<<1|1,n); //printf("-> %i\n",cyc); if(!cyc) { for(i=0;i<n*2;i+=2) if(dep[i]>=0) cnt[dep[i]]++; for(i=0;i<q;i++) if(k[i]<=2*n) sol[i]+=cnt[k[i]]; } else { vector<int> Ds; for(i=0;i<n*2;i+=2) if(dep[i]>=0) Ds.pb(dep[i]); sort(Ds.begin(),Ds.end()); j=0; for(i=0;i<q;i++) { while(j<Ds.size() && Ds[j]<=Qs[i].first) cnt[Ds[j]%cyc]++,j++; sol[Qs[i].second]+=cnt[Qs[i].first%cyc]; } } for(i=0;i<q;i++) answer(sol[i]); } /*int go[M],lo[M],dep[M]; vector<int> E[M]; void DFS(int u, int p) { for(int i=0;i<E[u].size();i++) { int v=E[u][i]; dep[v]=dep[u]+1; if(v!=p) DFS(v,p); } } pair<int,int> Qs[N]; int cnt[M],sol[N]; void count_routes(int n, int m, int p, int r[][2], int q, int k[]) { int i,j; for(i=0;i<q;i++) Qs[i].first=k[i],Qs[i].second=i; sort(Qs,Qs+q); for(i=0;i<n*2;i++) lo[i]=-1; for(i=0;i<n*2;i++) go[i]=-1; for(i=0;i<m;i++) { if(lo[r[i][0]<<1]==-1) lo[r[i][0]<<1]=i; else if(lo[r[i][0]<<1|1]==-1) lo[r[i][0]<<1|1]=i; if(lo[r[i][1]<<1]==-1) lo[r[i][1]<<1]=i; else if(lo[r[i][1]<<1|1]==-1) lo[r[i][1]<<1|1]=i; } for(i=0;i<n*2;i++) { int x=lo[i]; if(lo[i]==-1) x=lo[i^1]; int v=r[x][0]; if(v==i/2) v=r[x][1]; if(x==lo[v<<1]) go[i]=v<<1|1; else go[i]=v<<1; } for(i=0;i<2*n;i++) { E[go[i]].pb(i); //printf("%i -> %i\n",go[i],i); dep[i]=-1; } dep[p<<1]=0; DFS(p<<1,p<<1); if(dep[p<<1]==0) { for(i=0;i<2*n;i+=2) if(dep[i]>=0) cnt[dep[i]]++; for(i=0;i<q;i++) if(k[i]<M) sol[i]+=cnt[k[i]]; for(i=0;i<2*n;i+=2) if(dep[i]>=0) cnt[dep[i]]--; } else { int cyc=dep[p<<1]; dep[p<<1]=0; j=0; vector<int> Ds; for(i=0;i<2*n;i+=2) if(dep[i]>=0) Ds.pb(dep[i]); sort(Ds.begin(),Ds.end()); for(i=0;i<q;i++) { while(j<Ds.size() && Ds[j]<=Qs[i].first) cnt[Ds[j]%cyc]++,j++; sol[Qs[i].second]+=cnt[Qs[i].first%cyc]; } for(i=0;i<cyc;i++) cnt[i]=0; } for(i=0;i<2*n;i++) dep[i]=-1; dep[p<<1|1]=0; DFS(p<<1|1,p<<1|1); if(dep[p<<1|1]==0) { for(i=0;i<2*n;i+=2) if(dep[i]>=0) cnt[dep[i]]++; for(i=0;i<q;i++) if(k[i]<M) sol[i]+=cnt[k[i]]; for(i=0;i<2*n;i+=2) if(dep[i]>=0) cnt[dep[i]]--; } else { int cyc=dep[p<<1|1]; dep[p<<1|1]=0; //printf("%i :D\n",cyc); j=0; vector<int> Ds; for(i=0;i<2*n;i+=2) if(dep[i]>=0) Ds.pb(dep[i]); sort(Ds.begin(),Ds.end()); for(i=0;i<q;i++) { while(j<Ds.size() && Ds[j]<=Qs[i].first) cnt[Ds[j]%cyc]++,j++; sol[Qs[i].second]+=cnt[Qs[i].first%cyc]; } for(i=0;i<cyc;i++) cnt[i]=0; } for(i=0;i<q;i++) answer(sol[i]); }*/ //---------------------// /* int r[N][2],k[N]; int main() { int n,m,p,q,i; scanf("%i %i %i",&n,&m,&p); for(i=0;i<m;i++) scanf("%i %i",&r[i][0],&r[i][1]); scanf("%i",&q); for(i=0;i<q;i++) scanf("%i",&k[i]); count_routes(n,m,p,r,q,k); return 0; } */ //---------------------//

Compilation message (stderr)

garden.cpp: In function 'void DFS(int, int)':
garden.cpp:21:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<E[u].size();i++)
              ~^~~~~~~~~~~~
garden.cpp: In function 'void count_routes(int, int, int, int (*)[2], int, int*)':
garden.cpp:75:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    while(j<Ds.size() && Ds[j]<=Qs[i].first) cnt[Ds[j]%cyc]++,j++;
          ~^~~~~~~~~~
garden.cpp:98:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    while(j<Ds.size() && Ds[j]<=Qs[i].first) cnt[Ds[j]%cyc]++,j++;
          ~^~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...