#include<bits/stdc++.h>
#include "gardenlib.h"
#include "garden.h"
using namespace std;
pair<int,int> D[150001][31][2];
pair<int,int> mn[150001][2];
bool vis[1500001][2];
vector<pair<int,int>> adj[150001];
int dis[1500001][2];
int type[1500001][2];
void dfs(int v,int t) {
if (vis[v][t]) return;
int x = mn[v][!t].second;
int val = mn[v][!t].first;
if (val == mn[x][0].first) {
dfs(x,1);
if (dis[x][0] != -1)
dis[v][t] = dis[x][1] + 1,
type[v][t] = type[x][1];
}
else {
dfs(x,0);
if (dis[x][0] != -1)
dis[v][t] = dis[x][0] + 1,
type[v][t] = type[x][0];
}
}
int H;
int P1;
int fix[1500001][2];
pair<int,int> times[2];
int b;
void go(int v,int t) {
if (H && v == P1) {
times[b] = {H,t};
return;
}
if (fix[v][t]) return;
fix[v][t] = 1;
H++;
int x = mn[v][!t].second;
int val = mn[v][!t].first;
if (val == mn[x][0].first)
go(x,1);
else
go(x,0);
}
int cycle[150005][2];
void count_routes(int N, int M, int P, int R[][2], int Q, int G[]){
memset(dis,-1,sizeof dis);
P++;
for (int i = 0; i < M; i++) {
R[i][0]++;
R[i][1]++;
adj[R[i][0]].push_back({R[i][1],i + 1});
adj[R[i][1]].push_back({R[i][0],i+1});
}
dis[P][0] = dis[P][1] = 0;
vis[P][0] = vis[P][1] = 1;
type[P][1] = 1;
go(P,0);
H = 0;
b = 1;
go(P,1);
for (int i = 1; i <= N; i++) {
if (!vis[i][0]) dfs(i,0);
if (!vis[i][1]) dfs(i,1);
}
for (int i = 1; i <= N; i++) {
if (dis[i][0] != -1) {
cycle[i][0] = times[type[i][0]].first;
cycle[i][1] = times[times[type[i][0]].second].first;
}
}
for (int i = 1; i <= N; i++) {
if (adj[i].size() == 1) mn[i][0] = {adj[i][0].second,adj[i][0].first}, mn[i][1] = {adj[i][0].second,adj[i][0].first};
else mn[i][0] = {adj[i][0].second,adj[i][0].first}, mn[i][1] = {adj[i][1].second,adj[i][1].first};
}
for (int i = 1; i <= N; i++) {
D[i][0][0] = {mn[i][0].second,mn[i][0].first};
D[i][0][1] = {mn[i][1].second,mn[i][1].first};
}
for (int j = 1; j <= 30; j++) {
for (int i = 1; i <= N; i++) {
auto S = D[i][j-1][0];
int x = S.first;
int val = S.second;
if (val == mn[x][0].first) {
D[i][j][0] = D[x][j-1][1];
}
else D[i][j][0] = D[x][j-1][0];
S = D[i][j-1][1];
x = S.first;
val = S.second;
if (val == mn[x][0].first)
D[i][j][1] = D[x][j-1][1];
else D[i][j][1] = D[x][j-1][0];
}
}
for (int q = 0,k; q < Q; q++) {
k = G[q];
pair<int,int> cur;
int ans = 0;
for (int i = 1; i <= N; i++) {
cur = {i,0};
int x = dis[i][0];
if (dis[i][0] == -1 || k < x) continue;
if (k == x) ans++;
else {
k-=x;
int s = cycle[i][0] + cycle[i][1];
if ( s && (k%s == cycle[i][0] || k%s == cycle[i][0] ))
ans++;
}
}
answer(ans);
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
168 ms |
262148 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
168 ms |
262148 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
168 ms |
262148 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
