Submission #1104824

#TimeUsernameProblemLanguageResultExecution timeMemory
1104824sweedTropical Garden (IOI11_garden)C++14
0 / 100
61 ms80200 KiB
#include "garden.h" #include "gardenlib.h" #define pb emplace_back #include<bits/stdc++.h> using namespace std; vector<int>g[300005]; vector<int>g2[600005]; int jp=0; vector<int>g_rev[600005]; bool cycle=false; int c; map<int,bool>vs; int pp; void dfs(int u,int cnt) { if(vs[u]) { if(u==pp) { cycle = true; pp = cnt; } return ; } vs[u]=true; for(auto v:g2[u]) { dfs(v,cnt+1); } } int cnt_ans1[600005]; int cnt_ans2[600005]; void dfs1(int u,int cnt) { if(vs[u]) return ; vs[u] = true; cnt_ans1[u] = cnt; for(auto v:g_rev[u]) dfs1(v,cnt+1); } void dfs2(int u,int cnt) { if(vs[u]) return ; vs[u] = true; cnt_ans2[u] = cnt; for(auto v:g_rev[u]) dfs2(v,cnt+1); } void count_routes(int n, int m, int p, int R[][2], int Q, int G[]) { pp=p; for(int i=0;i<m;i++) { if(g[R[i][0]].size()<=2) g[R[i][0]].pb(R[i][1]); if(g[R[i][1]].size()<=2) g[R[i][1]].pb(R[i][0]); } for(int i=0;i<n;i++) { int v = g[i][0]; if(i==g[v][0]) g2[i].pb(v+n); else g2[i].pb(v); int vv; if(g[i].size()!=1) vv = g[i][1]; else vv = g[i][0]; if(i==g[vv][0]) g2[i+n].pb(vv+n); else g2[i+n].pb(vv); } for(int i=0;i<2*n;i++) { g_rev[g2[i][0]].pb(i); } dfs(p,0); bool cycle1 = cycle; int c1 = c; cycle=false; vs.clear(); dfs(n+p,0); vs.clear(); bool cycle2 = cycle; int c2 = c; dfs1(p,0); vs.clear(); dfs2(p+n,0); for(int k=0;k<Q;k++) { int d = G[k]; int ans=0; for(int i=0;i<n;i++) { bool ch=true; if(cycle1 and (d-cnt_ans1[i])%c1==0) { ans++; ch=false; } else if(d==cnt_ans1[i]) { ans++; ch=false; } if(!ch) continue; if(cycle2 and (d-cnt_ans2[i])%c2==0) { ans++; ch=false; } else if(d==cnt_ans2[i]) { ans++; ch=false; } // cout << ans << ' ' << i << endl; } // cout << endl; answer(ans); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...