#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 sum=0;
for(int i=0; i<2*N; ++i){
sum+=cnt[i];
}
assert(sum==N);
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){
//assert(1==0);
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;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
7544 KB |
Output is correct |
| 2 |
Correct |
9 ms |
7568 KB |
Output is correct |
| 3 |
Correct |
9 ms |
7516 KB |
Output is correct |
| 4 |
Incorrect |
8 ms |
7388 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 |
9 ms |
7568 KB |
Output is correct |
| 3 |
Correct |
9 ms |
7516 KB |
Output is correct |
| 4 |
Incorrect |
8 ms |
7388 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 |
9 ms |
7568 KB |
Output is correct |
| 3 |
Correct |
9 ms |
7516 KB |
Output is correct |
| 4 |
Incorrect |
8 ms |
7388 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
