#include "garden.h"
#include "gardenlib.h"
int best[150001][2];
int cyc;
int len[150001];
int time[150001][2];
bool in[150001];
bool proc[150001];
bool doing[150001];
int dfs(int v){
if(proc[v]) return time[v][1];
if(doing[v] == 1) return 1000000001;
doing[v] = 1;
time[v][1] = dfs(best[v][1]) + 1;
doing[v] = 0;
proc[v] = 1;
return time[v][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 v = R[i][0] + 1, u = R[i][1] + 1;
if(!best[v][0]) best[v][0] = u;
else if(!best[v][1]) best[v][1] = u;
if(!best[u][0]) best[u][0] = v;
else if(!best[u][1]) best[u][1] = v;
}
for(int i = 1; i <= N; i++)
if(!best[i][1]) best[i][1] = best[i][0];
int now = ++P;
while(!in[now]) {
in[now] = 1;
cyc++;
now = best[now][1];
}
if(now != P)
cyc = 1000000001;
proc[P] = 1;
for(int i = 1; i <= N; i++)
if(!proc[i])dfs(i);
for(int i = 0; i < N; i++){
time[i][0] = time[best[i][0]][1] + 1;
if(time[i][0] <= 150000)
len[time[i][0]]++;
}
for(int i = cyc; i <= N; i++)
len[i] += len[i - cyc];
for(int i = 0; i < Q; i++){
if(G[i] > N){
G[i] = N / cyc * cyc + G[i] % cyc;
if(G[i] > N) G[i] -= cyc;
}
if(G[i] < 0) answer(0);
else answer(len[G[i]]);
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
