#include "gardenlib.h"
// O O O O O O O O O O O O O O O OO O OO O OO O O O TTCH O TTTCH O TTTCH O O O O
#pragma GCC optimize("Ofast")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,popcnt,abm,mmx")
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <stdio.h>
#include <cstdio>
#include <math.h>
#include <cmath>
#include <string>
#include <cstring>
#include <queue>
#include <deque>
#include <random>
#include <iomanip>
#include <bitset>
#include <cassert>
// #include "grader.h"
using namespace std;
// void answer(int i) {
// cout << i << '\n';
// }
const int MAXN = 200 * 1000 + 228;
int n, m, p, q;
vector<int> g[MAXN];
int go[MAXN], sz[MAXN];
int ans[MAXN];
bool in_cycle[MAXN], used[MAXN], was[MAXN];
vector<int> cycle[MAXN];
int num[MAXN], ind[MAXN];
int h[MAXN], tin[MAXN], tout[MAXN], timer = 0;
int dist1[MAXN], dist2[MAXN];
int parent[MAXN];
void dfs(int v, int par, int gpar) {
parent[v] = gpar;
h[v] = (par == v ? 0 : h[par] + 1);
tin[v] = timer++;
for (int to : g[v]) {
if (in_cycle[to]) continue;
dfs(to, v, gpar);
}
tout[v] = timer++;
}
bool anc(int u, int v) {
return tin[u] <= tin[v] && tout[u] >= tout[v];
}
int get_dist(int v, int p) {
if (anc(p, v)) {
return h[v] - h[p];
}
int cur = 0;
if (in_cycle[p]) {
if (!in_cycle[v]) {
cur = h[v];
v = parent[v];
}
if (num[p] != num[v]) return -1;
if (ind[v] < ind[p]) cur += ind[p] - ind[v];
else cur += (int)cycle[num[p]].size() - ind[v] + ind[p];
} else return -1;
return cur;
}
void count_routes(int N, int M, int P, int R[][2], int Q, int G[]){
n = N;
m = M;
q = Q;
++P;
p = P;
for (int i = 0; i < m; ++i) {
++R[i][0], ++R[i][1];
g[R[i][0]].push_back(R[i][1]);
g[R[i][1]].push_back(R[i][0]);
}
for (int i = 1; i <= n; ++i) {
sz[i] = (int)g[i].size();
}
for (int i = 1; i <= n; ++i) {
int to = g[i][0];
if (g[to][0] == i && sz[to] > 1) {
go[i] = to + n;
if (sz[i] == 1) go[i + n] = to + n;
} else {
go[i] = to;
if (sz[i] == 1) go[i + n] = to + n;
}
if (sz[i] != 1) {
to = g[i][1];
if (g[to][0] == i && sz[to] > 1) {
go[n + i] = to + n;
} else {
go[n + i] = to;
}
}
}
for (int i = 1; i <= 2 * n; ++i) {
g[i].clear();
}
for (int i = 1; i <= 2 * n; ++i) {
g[go[i]].push_back(i);
}
int ptr = 0;
for (int i = 1; i <= 2 * n; ++i) {
vector<int> vvs;
int v = i;
was[v] = 1;
bool found = 0;
vvs.push_back(v);
while (!used[v]) {
used[v] = 1;
v = go[v];
vvs.push_back(v);
if (was[v]) {
found = 1;
break;
}
was[v] = 1;
}
for (int x : vvs) {
was[x] = 0;
}
if (found) {
++ptr;
int s = v;
do
{
cycle[ptr].push_back(v);
num[v] = ptr;
ind[v] = (int)cycle[ptr].size() - 1;
in_cycle[v] = 1;
v = go[v];
}
while(v != s);
}
}
for (int i = 1; i <= 2 * n; ++i) {
if (in_cycle[i]) {
dfs(i, i, i);
}
}
get_dist(1, P + n);
for (int v = 1; v <= n; ++v) {
dist1[v] = get_dist(v, P);
dist2[v] = get_dist(v, P + n);
}
int SZ1 = 0, SZ2 = 0;
if (in_cycle[P]) SZ1 = (int)cycle[num[P]].size();
if (in_cycle[n + P]) SZ2 = (int)cycle[num[n + P]].size();
for (int i = 0; i < Q; i++) {
bool ok = 0;
int k = G[i];
int ans = 0;
for (int v = 1; v <= n; ++v) {
ok = 0;
if (dist1[v] != -1) {
if (dist1[v] <= k) {
if (dist1[v] == k) ok = 1;
else if (in_cycle[P] && (k - dist1[v]) % SZ1 == 0) {
ok = 1;
}
}
}
if (!ok && dist2[v] != -1) {
if (dist2[v] <= k) {
if (dist2[v] == k) ok = 1;
else if (in_cycle[n + P] && (k - dist2[v]) % SZ2 == 0) {
ok = 1;
}
}
}
if (ok) {
++ans;
}
}
answer(ans);
}
}
// int G[100];
// int R[100][2];
// signed main() {
// cin >> n >> m >> p;
// for (int i = 0; i < m; ++i) {
// cin >> R[i][0] >> R[i][1];
// }
// cin >> q;
// for (int i = 0; i < q; ++i) {
// cin >> G[i];
// }
// count_routes(n, m, p, R, q, G);
// }
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
9976 KB |
Output is correct |
| 2 |
Correct |
15 ms |
9976 KB |
Output is correct |
| 3 |
Correct |
11 ms |
9976 KB |
Output is correct |
| 4 |
Correct |
11 ms |
9848 KB |
Output is correct |
| 5 |
Correct |
11 ms |
9848 KB |
Output is correct |
| 6 |
Correct |
12 ms |
9976 KB |
Output is correct |
| 7 |
Correct |
12 ms |
9848 KB |
Output is correct |
| 8 |
Correct |
12 ms |
9976 KB |
Output is correct |
| 9 |
Correct |
14 ms |
10104 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
9976 KB |
Output is correct |
| 2 |
Correct |
15 ms |
9976 KB |
Output is correct |
| 3 |
Correct |
11 ms |
9976 KB |
Output is correct |
| 4 |
Correct |
11 ms |
9848 KB |
Output is correct |
| 5 |
Correct |
11 ms |
9848 KB |
Output is correct |
| 6 |
Correct |
12 ms |
9976 KB |
Output is correct |
| 7 |
Correct |
12 ms |
9848 KB |
Output is correct |
| 8 |
Correct |
12 ms |
9976 KB |
Output is correct |
| 9 |
Correct |
14 ms |
10104 KB |
Output is correct |
| 10 |
Correct |
11 ms |
9848 KB |
Output is correct |
| 11 |
Correct |
26 ms |
13052 KB |
Output is correct |
| 12 |
Correct |
49 ms |
15064 KB |
Output is correct |
| 13 |
Correct |
64 ms |
23752 KB |
Output is correct |
| 14 |
Runtime error |
92 ms |
34552 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 15 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
9976 KB |
Output is correct |
| 2 |
Correct |
15 ms |
9976 KB |
Output is correct |
| 3 |
Correct |
11 ms |
9976 KB |
Output is correct |
| 4 |
Correct |
11 ms |
9848 KB |
Output is correct |
| 5 |
Correct |
11 ms |
9848 KB |
Output is correct |
| 6 |
Correct |
12 ms |
9976 KB |
Output is correct |
| 7 |
Correct |
12 ms |
9848 KB |
Output is correct |
| 8 |
Correct |
12 ms |
9976 KB |
Output is correct |
| 9 |
Correct |
14 ms |
10104 KB |
Output is correct |
| 10 |
Correct |
11 ms |
9848 KB |
Output is correct |
| 11 |
Correct |
26 ms |
13052 KB |
Output is correct |
| 12 |
Correct |
49 ms |
15064 KB |
Output is correct |
| 13 |
Correct |
64 ms |
23752 KB |
Output is correct |
| 14 |
Runtime error |
92 ms |
34552 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 15 |
Halted |
0 ms |
0 KB |
- |
