#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(x) begin(x), end(x)
#define sz(x) (int)x.size()
#define pb push_back
#include "gardenlib.h"
const int maxn = 300000;
vector<int> adj[maxn];
bool bl[maxn], vis[maxn];
int d[maxn];
void dfs(int s, int p){
if(vis[s]) return;
vis[s] = true;
if(p != -1) d[s] = d[p]+1;
for(auto u: adj[s]){
if(u == p or bl[u]) continue;
dfs(u, s);
}
}
void count_routes(int N, int M, int P, int R[][2], int Q, int G[]){
int n, m; n = N, m = M;
vector<pair<int, int>> vec[n];
int mn[n] = {};
for(int i=1; i<=m; i++){
int a, b; a = R[i-1][0], b = R[i-1][1];
vec[a].pb({b, i}); vec[b].pb({a, i});
if(mn[a] == 0) mn[a] = i;
if(mn[b] == 0) mn[b] = i;
}
int to[2*n] = {};
for(int a=0; a<n; a++){
auto [b, i] = vec[a][0];
if(mn[b] == i) to[a] = n+b;
else to[a] = b;
if(sz(vec[a]) >= 2){
auto [c, j] = vec[a][1];
if(mn[c] == j) to[n+a] = n+c;
else to[n+a] = c;
}
else{
if(mn[b] == i) to[n+a] = n+b;
else to[n+a] = b;
}
}
for(int a=0; a<2*n; a++){
adj[a].pb(to[a]); adj[to[a]].pb(a);
}
int p; p = P;
int q; q = Q;
int qry[q] = {};
for(int i=0; i<q; i++) qry[i] = G[i];
int ans[q] = {};
{
int p1 = to[p], p2 = to[to[p]];
while(p1 != p2){
p1 = to[p1];
p2 = to[to[p2]];
}
p2 = p;
while(p1 != p2){
p1 = to[p1];
p2 = to[p2];
}
fill(bl, bl+2*n, 0);
fill(vis, vis+2*n, 0);
vector<int> cyc;
cyc.pb(p1);
bl[p1] = 1;
int ok = 0;
if(p1 == p) ok = 1;
int x = to[p1];
while(x != p1){
if(x == p) ok = 1;
cyc.pb(x);
bl[x] = 1;
x = to[x];
}
int l = sz(cyc);
fill(d, d+2*n, -1);
if(ok){
d[p] = 0;
dfs(p, -1);
x = to[p];
int c = l-1;
while(x != p){
d[x] = c;
dfs(x, -1);
x = to[x];
c--;
}
}
else{
d[p] = 0;
dfs(p, -1);
}
for(int i=0; i<q; i++){
int k = qry[i];
for(int a=0; a<n; a++){
if(d[a] == -1) continue;
if(ok){
if((k-d[a])%l == 0) ans[i]++;
}
else{
if(k == d[a]) ans[i]++;
}
}
}
}
p = n+p;
{
int p1 = to[p], p2 = to[to[p]];
while(p1 != p2){
p1 = to[p1];
p2 = to[to[p2]];
}
p2 = p;
while(p1 != p2){
p1 = to[p1];
p2 = to[p2];
}
fill(bl, bl+2*n, 0);
fill(vis, vis+2*n, 0);
vector<int> cyc;
cyc.pb(p1);
bl[p1] = 1;
int ok = 0;
if(p1 == p) ok = 1;
int x = to[p1];
while(x != p1){
if(x == p) ok = 1;
cyc.pb(x);
bl[x] = 1;
x = to[x];
}
int l = sz(cyc);
fill(d, d+2*n, -1);
if(ok){
d[p] = 0;
dfs(p, -1);
x = to[p];
int c = l-1;
while(x != p){
d[x] = c;
dfs(x, -1);
x = to[x];
c--;
}
}
else{
d[p] = 0;
dfs(p, -1);
}
for(int i=0; i<q; i++){
int k = qry[i];
for(int a=0; a<n; a++){
if(d[a] == -1) continue;
if(ok){
if((k-d[a])%l == 0) ans[i]++;
}
else{
if(k == d[a]) ans[i]++;
}
}
}
}
for(int i=0; i<q; i++){
answer(ans[i]);
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
10832 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
10832 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
10832 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
