#include "garden.h"
#include <iostream>
#include <vector>
using namespace std;
const int N = 150005;
const int LOG = 30;
vector<int> g[N], path;
int up[LOG][2 * N], tocyc[2 * N], cyc[2 * N], cycsz[2 * N], toP[2][2 * N];
bool vis[2 * N];
int kth(int k, int node){
for(int i = LOG - 1;i >= 0;--i){
if(k >= (1 << i)){
k -= (1 << i);
node = up[i][node];
}
}
return node;
}
void dfs(int node){
path.push_back(node);
vis[node] = 1;
if(!vis[up[0][node]]){
dfs(up[0][node]);
}
else{
if(!cycsz[up[0][node]]){
int sz = 1, cnt = 0;
for(int i = (int)path.size() - 1;i >= 0 && path[i] != up[0][node];--i){
sz++;
}
for(int i = (int)path.size() - 1;i >= 0 && path[i] != up[0][node];--i){
cycsz[path[i]] = sz;
cyc[path[i]] = cnt++;
}
cycsz[up[0][node]] = sz;
cyc[up[0][node]] = cnt++;
}
}
if(cycsz[node])return;
cycsz[node] = cycsz[up[0][node]];
tocyc[node] = tocyc[up[0][node]] + 1;
}
void answer(int x);
// void answer(int x){
// cout << x << '\n';
// }
void count_routes(int n, int m, int p, int r[][2], int q, int k[]){
for(int i = 0;i < m;++i){
int u = r[i][0], v = r[i][1];
g[u].push_back(v);
g[v].push_back(u);
}
for(int i = 0;i < n;++i){
if(g[i].empty())continue;
int v = g[i][0];
if(g[v][0] == i){
up[0][i << 1] = ((v << 1) | 1);
}
else{
up[0][i << 1] = (v << 1);
}
if(g[i].size() >= 2)v = g[i][1];
else v = g[i][0];
if(g[v][0] == i){
up[0][(i << 1) | 1] = ((v << 1) | 1);
}
else{
up[0][(i << 1) | 1] = (v << 1);
}
}
for(int i = 1;i < LOG;++i){
for(int j = 0;j < 2 * n;++j){
up[i][j] = up[i - 1][up[i - 1][j]];
}
}
for(int i = 0;i < 2 * n;++i){
if(!vis[i]){
dfs(i);
path.clear();
}
}
// for(int i = 0;i < 2 * n;++i){
// cout << i << " " << cyc[i] << '\n';
// }
for(int i = 0;i < 2 * n;++i){
for(int j = 0;j < 2;++j){
int P = ((p << 1) | j);
if(tocyc[P]){
toP[j][i] = max(0, tocyc[i] - tocyc[P]);
}
else{
int X = kth(tocyc[i], i);
toP[j][i] = tocyc[i] + (cyc[X] - cyc[P] + cycsz[P]) % cycsz[P];
}
if(kth(toP[j][i], i) != P)toP[j][i] = -1;
}
}
for(int i = 0;i < q;++i){
int K = k[i], cnt = 0;
for(int j = 0;j < 2 * n;j += 2){
for(int l = 0;l < 2;++l){
// cout << j / 2 << ": " << toP[l][j] << endl;
if(toP[l][j] == -1)continue;
int P = ((p << 1) | l);
if(tocyc[P]){
cnt += (K == toP[l][j]);
}
else{
cnt += (K % cycsz[P] == toP[l][j] % cycsz[P]);
}
}
}
answer(cnt);
}
}
// int main(){
// ios_base::sync_with_stdio(0);
// cin.tie(0);
// int n, m, p;
// cin >> n >> m >> p;
// int r[m][2];
// for(int i = 0;i < m;++i){
// int u, v;
// cin >> u >> v;
// r[i][0] = u, r[i][1] = v;
// }
// int q;
// cin >> q;
// int k[q];
// for(int i = 0;i < q;++i){
// cin >> k[i];
// }
// count_routes(n, m, p, r, q, k);
// }
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |