Submission #16481

#TimeUsernameProblemLanguageResultExecution timeMemory
16481khsoo01Tropical Garden (IOI11_garden)C++98
69 / 100
5047 ms31288 KiB
#include<bits/stdc++.h> #include "garden.h" #include "gardenlib.h" #define INF 0x7fffffff using namespace std; vector<int>cg[300005],cn[300005]; int n,m,p,ed[300005][2],cur,flag,vis[300005],cnt; int dist[2][300005],cyc_len[2]; bool state,in_cyc[2]; void find_cyc(int idx) { if(vis[idx]==1) { if(!in_cyc[state] && idx!=cn[p][state]) return; in_cyc[state]=true; cyc_len[state]++; } if(vis[idx]==2) return; vis[idx]++; find_cyc(cn[ed[idx][1]][(cg[ed[idx][1]][0]==ed[idx][0] && cg[ed[idx][1]].size()>1)?1:0]); vis[idx]=0; } int find_dist(int idx) { if(cn[p][state]==idx) return dist[state][idx]=0; if(vis[idx]) return dist[state][idx]; vis[idx]++; return dist[state][idx]=find_dist(cn[ed[idx][1]][(cg[ed[idx][1]][0]==ed[idx][0] && cg[ed[idx][1]].size()>1)?1:0])+1; } void count_routes(int N, int M, int P, int R[][2], int Q, int G[]) { int i,j,tmp; n=N; m=M; p=P; for(i=0;i<m;i++) { ed[i][0]=R[i][0]; ed[i][1]=R[i][1]; ed[i+m][0]=R[i][1]; ed[i+m][1]=R[i][0]; cg[ed[i][0]].push_back(ed[i][1]); cn[ed[i][0]].push_back(i); cg[ed[i][1]].push_back(ed[i][0]); cn[ed[i][1]].push_back(i+m); dist[0][i]=-INF; dist[1][i]=-INF; dist[0][i+M]=-INF; dist[1][i+M]=-INF; } state=0; find_cyc(cn[p][0]); state=1; find_cyc(cn[p][1]); state=0; for(i=0;i<2*m;i++) { if(vis[i])continue; find_dist(i); } state=1; memset(vis,0,sizeof(vis)); for(i=0;i<2*m;i++) { if(vis[i])continue; find_dist(i); } for(i=0;i<Q;i++) { cnt=0; for(j=0;j<n;j++) { tmp=cn[j][0]; if(dist[0][tmp]==G[i]){ cnt++; continue; } if(dist[1][tmp]==G[i]){ cnt++; continue; } if(in_cyc[0] && dist[0][tmp]>=0 && dist[0][tmp]<G[i] && (G[i]-dist[0][tmp])%cyc_len[0]==0) { cnt++; continue; } if(in_cyc[1] && dist[1][tmp]>=0 && dist[1][tmp]<G[i] && (G[i]-dist[1][tmp])%cyc_len[1]==0) { cnt++; continue; } } answer(cnt); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...