This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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];
void dfs1(int v){
if(proc[v][0]) return;
proc[v][0] = 1;
if(v == p) return;
dfs1(to[v]);
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]);
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, 0x3f, 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 * 2; i++){
dfs1(i);
dfs0(i);
}
cyc[0] = 1 + t[to[p]][0];
cyc[1] = 1 + t[to[n + p]][1];
for(int j = 0; j < q; j++){
int res = 0;
for(int i = 0; i < n; i++){
if((t[i][0] < 0x3f3f3f3f && (g[j] - t[i][0]) % cyc[0] == 0 && g[j] >= t[i][0]) || (t[i][1] < 0x3f3f3f3f && g[j] >= t[i][1] && (g[j] - t[i][1]) % cyc[1] == 0)) res++;
}
answer(res);
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |