Submission #166096

#TimeUsernameProblemLanguageResultExecution timeMemory
166096DavidDamianTropical Garden (IOI11_garden)C++11
100 / 100
2889 ms36784 KiB
#include "garden.h" #include "gardenlib.h" #include <iostream> #include<vector> using namespace std; vector<int> adjList[300005]; vector<int> original[150005]; short vis[300005]; void buildGraph(int N) { for(int u=0;u<N;u++){ int v=original[u][0]; //Principal edge if(original[v][0]!=u || original[v].size()==1){ adjList[v].push_back(u); } else{ adjList[v+N].push_back(u); } if(original[u].size()==1) continue; v=original[u][1]; //Secondary edge if(original[v][0]!=u || original[v].size()==1){ adjList[v].push_back(u+N); } else{ adjList[v+N].push_back(u+N); } } } int color[300005]; int d[300005][2]; int C[2]={-1,-1}; //Cycle Size int inCycle[2]; int t=0; void dfs(int u) { color[u]=1; for(int v: adjList[u]){ if(color[v]==0){ d[v][t]=d[u][t]+1; dfs(v); } else if(color[v]==1){ C[t]=d[u][t]+1; inCycle[t]=1; } } color[u]=-1; } void count_routes(int N, int M, int P, int R[][2], int Q, int G[]) { for(int i=0;i<M;i++){ int u=R[i][0]; int v=R[i][1]; original[u].push_back(v); original[v].push_back(u); } buildGraph(N); for(int i=0;i<2*N;i++){ d[i][0]=d[i][1]=1000000000; } d[P][0]=0; dfs(P); t++; for(int i=0;i<2*N;i++){ color[i]=0; } d[P+N][1]=0; dfs(P+N); /*for(int i=0;i<2*N;i++){ cout<<d[i][0]<<" "<<d[i][1]<<endl; }*/ //cout<<inCycle[0]<<" "<<C[0]<<endl; //cout<<inCycle[1]<<" "<<C[1]<<endl; for(int i=0;i<Q;i++){ int k=G[i]; int total=0; for(int u=0;u<N;u++){ for(int j=0;j<2;j++){ if(d[u][j]==1000000000) continue; //Not reachable if(inCycle[j]){ int D=k-d[u][j]; if(D>=0){ if(D%C[j]==0) total++; } } else{ int D=k-d[u][j]; //Distance is exactly the same if(D==0) total++; } } } answer(total); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...