#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1.5e5 + 5, inf = 1e9 + 5;
//const int maxn = 15, inf = 1e9 + 5;
struct edge { int v, id; };
bool cmp(const edge &a, const edge &b) { return a.id < b.id; }
struct ans { int a, b; ans(int A = inf-1, int B = inf):a(A), b(B) {} };
vector<edge> g[maxn];
int nx[maxn*2], vis[maxn*2], col[maxn*2];
vector<int> pv[maxn*2], len(maxn*2, inf);
vector<ans> v[maxn*2];
void dfs(int u, const ans &a)
{
vis[u] = true, v[u].push_back(a);
for (int i : pv[u])
{
if (vis[i]) continue;
dfs(i, ans(a.a+1, a.b));
}
}
void count_routes(int n, int m, int p, int e[][2], int q, int qu[])
{
for (int i = 0; i < m; i++) g[e[i][0]].push_back({e[i][1], i}), g[e[i][1]].push_back({e[i][0], i});
for (int i = 0; i < n; i++)
{
sort(g[i].begin(), g[i].end(), cmp);
if (g[i].size() < 2) g[i].push_back(g[i][0]);
}
for (int l = 0; l < 2; l++) for (int i = 0; i < n; i++)
{
nx[l*n+i] = g[i][l].v+(g[i][l].id == g[g[i][l].v][0].id)*n;
pv[nx[l*n+i]].push_back(l*n+i);
}
int c = 0;
for (int i = 0; i < 2*n; i++)
{
if (vis[i]) continue;
c++;
int vr = i, cnt = 1;
while (!col[vr]) vis[vr] = cnt++, col[vr] = c, vr = nx[vr];
if (col[vr] != c) continue; // tento cyklus sme uz nasli
int l = cnt - vis[vr];
len[vr] = l; int v2 = nx[vr];
while (vr != v2) len[v2] = l, v2 = nx[v2];
}
for (int l = 0; l < 2; l++)
{
memset(vis, 0, sizeof(vis));
dfs(l*n+p, ans(0, len[l*n+p]));
}
for (int i = 0; i < q; i++)
{
int cnt = 0;
vector<int> kt;
for (int j = 0; j < n; j++)
{
bool ok = false;
for (const ans &a : v[j]) if ((qu[i] - a.a) % a.b == 0) ok = true;
cnt += ok;
if (ok) kt.push_back(j);
}
answer(cnt);
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
20528 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
20528 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
20528 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
