#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
using namespace std;
int n, p;
int to[300005];
int best[150005][2];
bool proc[300005][2];
int cyc[2];
int t[300005][2];
bool in[300005];
void dfs1(int v){
if(proc[v][0]) return;
proc[v][0] = 1;
if(v == p) return;
dfs1(to[v]);
if(t[to[v]][0] == -1) t[v][0] = -1;
else t[v][0] = t[to[v]][0] + 1;
}
void dfs0(int v){
if(proc[v][1]) return;
proc[v][1] = 1;
if(v == p + n) return;
dfs0(to[v]);
if(t[to[v]][1] == -1) t[v][1] = -1;
else t[v][1] = t[to[v]][1] + 1;
}
void count_routes(int n, int m, int p, int r[][2], int q, int g[]){
memset(best, -1, sizeof best);
memset(t, -1, sizeof t);
for(int i = 0; i < m; i++){
int v = r[i][0], u = r[i][1];
if(best[v][0] == -1) best[v][0] = u;
else if(best[v][1] == -1) best[v][1] = u;
if(best[u][0] == -1) best[u][0] = v;
else if(best[u][1] == -1) best[u][1] = v;
}
::n = n;
::p = p;
for(int i = 0; i < n; i++)
if(best[i][1] == -1) best[i][1] = best[i][0];
for(int i = 0; i < n; i++){
to[i] = best[i][0] + n * (best[best[i][0]][0] == i);
to[i + n] = best[i][1] + n * (best[best[i][1]][0] == i);
}
t[p][0] = 0;
t[p + n][1] = 0;
for(int i = 0; i < n; i++){
dfs1(i);
dfs0(i);
}
for(int j = 0 ; j < 2; j++){
memset(in, 0, sizeof in);
int v = to[p + j * n];
cyc[j] = 1;
while(v != p + j * n){
in[v] = 1;
cyc[j]++;
v = to[v];
if(in[v] == 1){
cyc[j] = 1000000001;
break;
}
}
}
for(int j = 0; j < q; j++){
int res = 0;
for(int i = 0; i < n; i++){
if((g[j] - t[i][0]) % cyc[0] == 0 || (g[j] - t[i][1]) % cyc[1] == 0) res++;
}
answer(res);
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
4188 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
4188 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
4188 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
