#include "garden.h"
#include "gardenlib.h"
#include <cstdio>
#include <vector>
#include <initializer_list>
using namespace std;
const int INF = 0x3f3f3f3f;
const int MAXN = 151515;
int N;
int minv1[MAXN], minv2[MAXN];
int outlist[2*MAXN];
vector<int> inlist[2*MAXN];
bool visit[2*MAXN];
int ans1[2*MAXN], ans2[2*MAXN];
void run(int P, int dist, int *ans, int &res, int oP)
{
if(visit[P])
{
if(P == oP) res = dist;
return;
}
visit[P] = true;
if(P<N) ans[dist]++;
for(auto x: inlist[P])
run(x, dist+1, ans, res, oP);
}
void count_routes(int _N, int M, int P, int R[][2], int Q, int G[])
{
N = _N;
for(int i=0; i<N; ++i) minv1[i] = minv2[i] = -1;
for(int i=0; i<M; ++i)
{
int u = R[i][0], v = R[i][1];
for(int x: {u, v})
{
int y = u+v-x;
if(minv1[x] == -1) minv1[x] = y;
else if(minv2[x] == -1) minv2[x] = y;
}
}
for(int i=0; i<N; ++i) if(minv2[i] == -1) minv2[i] = minv1[i];
for(int i=0; i<2*N; ++i)
{
int to = (i<N)?minv1[i%N]:minv2[i%N];
if(i%N == minv1[to]) to += N;
outlist[i] = to;
inlist[to].push_back(i);
}
int res1 = 0x3f3f3f3f, res2 = 0x3f3f3f3f;
run(P, 0, ans1, res1, P);
for(int i=0; i<2*N; ++i) visit[i] = false;
run(P+N, 0, ans2, res2, P+N);
for(int i=2*N-1; i>=res1; --i)
ans1[i-res1] += ans1[i];
for(int i=2*N-1; i>=res2; --i)
ans2[i-res2] += ans2[i];
for(int i=0; i<Q; ++i)
{
int ans = 0;
if(G[i] < 2*N) ans += ans1[G[i]];
else
{
int maxidx = (G[i]-(2*N-1))%res1 + (2*N-1) - res1;
if(maxidx >= 0) ans += ans1[maxidx];
}
if(G[i] < 2*N) ans += ans2[G[i]];
else
{
int maxidx = (G[i]-(2*N-1))%res2 + (2*N-1) - res2;
if(maxidx >= 0) ans += ans2[maxidx];
}
answer(ans);
}
return;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
7800 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
7800 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
7800 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
