| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 70930 | aleksam | Tropical Garden (IOI11_garden) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
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<2*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;
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){
answer(cumcnt[ G[i]%cyclen+2*N-cyclen]);
//cout<<cumcnt[ G[i]%cyclen+2*N-cyclen];
}
else {
answer(cumcnt[G[i]]);
//cout<<cumcnt[G[i]];
}
}
return;
}