# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
70939 | 2018-08-23T19:41:40 Z | aleksam | Tropical Garden (IOI11_garden) | C++14 | 8 ms | 7548 KB |
#include <bits/stdc++.h> #include "gardenlib.h" #define MAX_N 150000 using namespace std; vector<int> adj[MAX_N*2]; int best[MAX_N][2]; int dist[2][2*MAX_N]; bool mark[2][2*MAX_N]; int p, cyclen, num; int cnt[2*MAX_N]; int cumcnt[2*MAX_N]; void DFS(int u){ int d=adj[u].size(); for(int i=0; i<d; ++i){ if(!mark[num][adj[u][i]]){ mark[num][adj[u][i]]=1; dist[num][adj[u][i]]=dist[num][u]+1; DFS(adj[u][i]); } if(adj[u][i]==p){ cyclen=dist[num][u]+1; } } } void count_routes(int N, int M, int P, int R[][2], int Q, int G[]){ //u adj cuvamo sva temena koja se ulivaju u i //prvo odredjujemo najlepse putanje svakom temenu for(int i=0; i<N; ++i){ best[i][0]=best[i][1]=-1; } for(int i=0; i<M; ++i){ if(best[R[i][0]][0]==-1){ best[R[i][0]][0]=R[i][1]; } else{ if(best[R[i][0]][1]==-1){ best[R[i][0]][1]=R[i][1]; } } if(best[R[i][1]][0]==-1){ best[R[i][1]][0]=R[i][0]; } else{ if(best[R[i][1]][1]==-1){ best[R[i][1]][1]=R[i][0]; } } } for(int i=0; i<N; ++i){ //Odredjujemo gde ide cvor i if(best[best[i][0]][0]==i && best[best[i][0]][1]!=-1){ adj[best[i][0]+N].push_back(i); } else adj[best[i][0]].push_back(i); if(best[i][1]==-1)continue; if(best[best[i][1]][0]==i && best[best[i][0]][1]!=-1){ adj[best[i][1]+N].push_back(i+N); } else adj[best[i][1]].push_back(i+N); } /*for(int i=0; i<2*N; ++i){ printf("adj[%d]:", i); for(int j=0; j<adj[i].size(); ++j){ printf("%d ", adj[i][j]); } printf("\n"); }*/ mark[0][P]=1; p=P; cyclen=-1; dist[0][P]=0; DFS(P); num=1; mark[1][P+N]=1; p=P+N; dist[1][P+N]=0; DFS(P+N); for(int i=0; i<N; ++i){ //printf("dist:%d %d\n", dist[0][i], dist[1][i]); if(i<N){ cnt[dist[0][i]]++; cnt[dist[1][i]]++; } } /*for(int i=0; i<N; ++i){ printf("cnt:%d\n", cnt[i]); }*/ cnt[0]=1;int valu=1/0; if(cyclen==-1){ for(int i=0; i<Q; ++i){ answer(cnt[G[i]]); //cout<<cnt[G[i]]; } return; } for(int i=0; i<2*N; ++i){ cumcnt[i]=cnt[i]; if(i>=cyclen) cumcnt[i]+=cumcnt[i-cyclen]; } for(int i=0; i<Q; ++i){ if(G[i]>=2*N){ int val=G[i]%cyclen + 2*N - (2*N)%cyclen; while(val>2*N)val-=cyclen; answer(cumcnt[ val]); //cout<<cumcnt[ G[i]%cyclen+2*N-cyclen]; } else { answer(cumcnt[G[i]]); //cout<<cumcnt[G[i]]; } } return; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 8 ms | 7544 KB | Output is correct |
2 | Correct | 8 ms | 7544 KB | Output is correct |
3 | Correct | 8 ms | 7548 KB | Output is correct |
4 | Incorrect | 8 ms | 7416 KB | Output isn't correct |
5 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 8 ms | 7544 KB | Output is correct |
2 | Correct | 8 ms | 7544 KB | Output is correct |
3 | Correct | 8 ms | 7548 KB | Output is correct |
4 | Incorrect | 8 ms | 7416 KB | Output isn't correct |
5 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 8 ms | 7544 KB | Output is correct |
2 | Correct | 8 ms | 7544 KB | Output is correct |
3 | Correct | 8 ms | 7548 KB | Output is correct |
4 | Incorrect | 8 ms | 7416 KB | Output isn't correct |
5 | Halted | 0 ms | 0 KB | - |