#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[2], num;
int cnt[2][2*MAX_N];
int cumcnt[2][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[num]=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][1]][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[0]=cyclen[1]=-1;
dist[0][P]=0;
DFS(P);
//cout<<cyclen[0]<<endl;
num=1;
mark[1][P+N]=1;
p=P+N;
dist[1][P+N]=0;
DFS(P+N);
//cout<<cyclen[1]<<endl;
//if(cyclen[1]>0)cnt[1][0]=1;
//if(cyclen[0]>0)cnt[0][0]=1;
for(int i=0; i<2*N; ++i){
//printf("dist:%d %d\n", dist[0][i], dist[1][i]);
if(i<N){
if(dist[0][i])
cnt[0][dist[0][i]]++;
if(dist[1][i])
cnt[1][dist[1][i]]++;
}
}
for(int i=0; i<N; ++i){
//printf("cnt:%d %d\n", cnt[0][i], cnt[1][i]);
}
/*int sum=0;
for(int i=0; i<2*N; ++i){
sum+=cnt[i];
}*/
//assert(sum==N);
if(cyclen[0]==-1 && cyclen[1]==-1){
for(int i=0; i<Q; ++i){
answer(cnt[0][G[i]]+cnt[1][G[i]]);
//cout<<cnt[G[i]];
}
return;
}
for(int i=0; i<2*N; ++i){
cumcnt[0][i]=cnt[0][i];
if(i>=cyclen[0] && cyclen[0]!=-1)
cumcnt[0][i]+=cumcnt[0][i-cyclen[0]];
}
for(int i=0; i<2*N; ++i){
if(cyclen[1]==-1)break;
cumcnt[1][i]=cnt[1][i];
if(i>=cyclen[1] && cyclen[1]!=-1)
cumcnt[1][i]+=cumcnt[1][i-cyclen[1]];
}
for(int i=0; i<3*N; ++i){
//printf("cumcnt:%d %d\n", cumcnt[0][i], cumcnt[1][i]);
}
int cyc=max(cyclen[0], cyclen[1]);
for(int i=0; i<Q; ++i){
if(G[i]>=2*N){
int val=G[i]%cyc + 2*N - ((2*N)%cyc);
while(val>=2*N)val-=cyc;
answer(cumcnt[0][val]+cumcnt[1][val]);
//cout<<cumcnt[ G[i]%cyclen+2*N-cyclen];
}
else {
answer(cumcnt[0][G[i]]+cumcnt[1][G[i]]);
//cout<<cumcnt[G[i]];
}
}
return;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
7544 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
7544 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
7544 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
