Submission #260185

#TimeUsernameProblemLanguageResultExecution timeMemory
260185amiratouTropical Garden (IOI11_garden)C++14
100 / 100
3971 ms49388 KiB
#include "garden.h" #include "gardenlib.h" #include <bits/stdc++.h> using namespace std; #define fi first #define se second #define sz(x) (int)(x.size()) #define pb push_back const int MX = 450005,L=30; vector<pair<int,int> > vec[150005]; vector<int> res[MX],queries[MX],dp,anc; int nxt[MX],d[MX],rf[MX],g[2002],ans[2002],edge[150005][2],r,no,m,Tar; bitset<MX> vis; void dfs(int node){ rf[node]=r; vis[node]=1; if(node>=(2*m)) dp.pb(node); for(auto it:res[node]) if(it!=no)d[it]=d[node]+1,dfs(it); } void solve(int node){ for(auto it:queries[node]){ assert(sz(anc)>=g[it]); int final=anc[sz(anc)-g[it]]; ans[it]+=(((final>=m)?edge[final-m][0]:edge[final][1])==Tar); } anc.pb(node); for(auto it:res[node]) if(it!=no)solve(it); anc.pop_back(); } void count_routes(int N, int M, int P, int R[][2], int Q, int G[]) { m=M,Tar=P; for (int i = 0; i < Q; ++i) g[i]=G[i]; for (int i = 0; i < M; ++i) { edge[i][0]=R[i][0]; edge[i][1]=R[i][1]; vec[R[i][0]].pb({R[i][1],i}); vec[R[i][1]].pb({R[i][0],M+i}); } for (int i = 0; i < N; ++i) { multiset<pair<int,int> > myset; for (int j = 0; j < sz(vec[i]); ++j) { int val=vec[i][j].se-((vec[i][j].se>=M)?M:0); myset.insert({val,j}); } for (int j = 0; j < sz(vec[i]); ++j) { int val=vec[i][j].se-((vec[i][j].se>=M)?M:0); int c=val+((vec[i][j].se>=M)?0:M); myset.erase(myset.find({val,j})); if(!sz(myset))nxt[c]=vec[i][j].se; else nxt[c]=vec[i][myset.begin()->se].se; myset.insert({val,j}); } nxt[i+2*M]=vec[i][myset.begin()->se].se; } for (int i = 0; i < 2*M+N; ++i) if(nxt[i]!=-1)res[nxt[i]].pb(i); for (int i = 0; i < N; ++i) { if(vis[i+2*M])continue; int node=i+2*M,st,p; while(1){ vis[node]=1; node=nxt[node]; if(vis[node])break; } vector<int> cycle={node}; p=node,st=nxt[node]; while(st!=node){ cycle.pb(st); no=p,r=sz(cycle)-1,dfs(st); p=st; st=nxt[st]; } no=cycle.back(),r=0,dfs(node); for(auto it:dp){ for (int j = 0; j < Q; ++j) { if(d[it]>G[j]) queries[it].pb(j); else{ int rm=G[j]-d[it]; int final=cycle[(rf[it]+rm)%sz(cycle)]; assert(final<(2*M)); ans[j]+=(((final>=M)?R[final-M][0]:R[final][1])==P); } } } for (int j = 0; j < sz(cycle); ++j) { no=cycle[(j+sz(cycle)-1)%sz(cycle)]; solve(cycle[j]); } dp.clear(); } for (int i = 0; i < Q; ++i) answer(ans[i]); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...