#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 150005, maxm = 150005, INF = 1e9;
int n, m, p;
vector<int> adj[maxn];
int vis[maxn][2];
int dist[maxn][2][2];
vector<pair<int,int>> track;
int cyclesz[2] = {INF, INF};
int dfs(int u) {
int id = (track.size()>0 && track.back().first==adj[u][0] && adj[u].size()>1);
// cout << u << " " << id << " " << vis[u][id] << endl;
if (vis[u][id]==-3) return id;
if (vis[u][id]==-2) {
// cout << u << " " << id << endl;
vector<pair<int,int>> c;
reverse(track.begin(), track.end());
for (auto [i, j]:track) {
c.push_back({i, j});
if (i==u && j==id) break;
}
int sz = c.size(), pos = -1;
// cout << sz << endl;
// for (auto [i, j]:c) cout << i << " " << j << endl;
for (int i=0;i<sz;i++) if (c[i].first==p && c[i].second==0) pos = i;
if (pos!=-1) {
cyclesz[0] = sz;
for (int i=0;i<sz;i++) {
int cur = (i+p)%sz;
dist[c[cur].first][c[cur].second][0] = i;
}
}
pos = -1;
for (int i=0;i<sz;i++) if (c[i].first==p && c[i].second==1) pos = i;
if (pos!=-1) {
// cout << pos << endl;
cyclesz[1] = sz;
for (int i=0;i<sz;i++) {
int cur = (i+pos)%sz;
dist[c[cur].first][c[cur].second][1] = i;
// cout << "cost " << c[cur].first << " " << c[cur].second << " " << i << endl;
}
}
return id;
}
vis[u][id] = -2;
track.push_back({u, id});
int v = adj[u][id];
int nxt = dfs(v);
for (int i=0;i<=1;i++) {
if (dist[u][id][i]==-1 && dist[v][nxt][i]!=-1) dist[u][id][i] = dist[v][nxt][i] + 1;
}
if (u==p) dist[u][id][id] = 0;
vis[u][id] = -3;
return id;
}
void count_routes(int N, int M, int P, int R[][2], int Q, int G[]) {
n = N, m = M, p = P;
for (int i=0;i<m;i++) {
int u = R[i][0], v = R[i][1];
if (adj[u].size()<2) adj[u].push_back(v);
if (adj[v].size()<2) adj[v].push_back(u);
}
for (int i=0;i<n;i++) vis[i][0] = vis[i][1] = dist[i][0][0] = dist[i][1][0] = dist[i][0][1] = dist[i][1][1] = -1;
for (int i=0;i<n;i++) if (vis[i][0]==-1) {
track.clear();
dfs(i);
}
// cout << cyclesz[0] << " " << cyclesz[1] << endl;
for (int i=0;i<Q;i++) {
int x = G[i];
int ans = 0;
for (int i=0;i<n;i++) {
bool add = false;
for (int j=0;j<=1;j++) {
if (dist[i][0][j]!=-1 && (x-dist[i][0][j])%cyclesz[j]==0) add = true;
// if (x==1) cout << dist[i][0][i] << " ";
}
// if (x==1) cout << endl;
ans += add;
}
answer(ans);
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
6488 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
6488 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
6488 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
