#include<bits/stdc++.h>
#include "garden.h"
#include "gardenlib.h"
using namespace std;
const int INF = 1e9 + 7;
const int MAXN = 300010;
const int MAXQ = 2010;
int N, M, P, R[MAXN][2], Q, G[MAXQ];
int n, idCycle[MAXN], idInCycle[MAXN], parCycle[MAXN], adj[MAXN], depth[MAXN], quantity[MAXN];
int in[MAXN], mark[MAXN], dist[MAXN], comp;
bool inCycle[MAXN], outCycle[MAXN];
queue<int> q;
vector<int> v, graph[MAXN];
void functional_graph()
{
for(int i = 0; i < 2 * n; i++)
if(!in[i]) q.push(i);
while(!q.empty())
{
int cur = q.front(); q.pop();
int nex = adj[cur];
v.push_back(cur);
outCycle[cur] = true;
idInCycle[cur] = -1;
in[nex]--;
if(!in[nex]) q.push(nex);
}
for(int i = 0; i < 2 * n; i++)
{
if(outCycle[i] || inCycle[i]) continue;
inCycle[i] = true;
parCycle[i] = i;
idCycle[i] = ++comp;
idInCycle[i] = 0;
int cur = adj[i], id = 1;
while(cur != i)
{
inCycle[cur] = true;
parCycle[cur] = cur;
idCycle[cur] = comp;
idInCycle[cur] = id++;
cur = adj[cur];
}
quantity[comp] = id;
}
for(int i = v.size() - 1; i >= 0; i--)
{
int cur = v[i];
parCycle[cur] = parCycle[adj[cur]];
depth[cur] = depth[adj[cur]] + 1;
idCycle[cur] = idCycle[adj[cur]];
}
}
void count_routes(int n1, int m, int p, int r[][2], int queries, int g[])
{
n = n1;
for(int i = 0; i < 2 * n; i++) adj[i] = -1;
for(int i = 0; i < m; i++)
{
int u = r[i][0];
int v = r[i][1];
if(!mark[u] && !mark[v])
{
adj[2 * u] = 2 * v + 1;
adj[2 * v] = 2 * u + 1;
mark[u] = 1, mark[v] = 1;
}
else if(mark[u] + mark[v] == 1)
{
if(mark[v] == 1) swap(u, v);
adj[2 * u + 1] = 2 * v + 1;
adj[2 * v] = 2 * u;
mark[u] = 2, mark[v] = 1;
}
else if(mark[u] == 1 && mark[v] == 1)
{
adj[2 * u + 1] = 2 * v;
adj[2 * v + 1] = 2 * u;
mark[u] = mark[v] = 2;
}
else if(mark[u] == 2 && mark[v] == 2) continue;
else if(mark[u] == 2 || mark[v] == 2)
{
if(mark[v] == 2) swap(u, v);
if(mark[v] == 0) adj[2 * v] = 2 * u, mark[v] = 1;
if(mark[v] == 1) adj[2 * v + 1] = 2 * u, mark[v] = 2;
}
}
for(int i = 0; i < n; i++)
if(adj[2 * i + 1] == -1)
adj[2 * i + 1] = adj[2 * i];
for(int i = 0; i < 2 * n; i++)
{
// printf("%d -> %d\n", i, adj[i]);
in[adj[i]]++;
}
functional_graph();//see();
p *= 2;
int idP = (inCycle[p]) ? idInCycle[p] : -1;
int idP2 = (inCycle[p + 1]) ? idInCycle[p + 1] : -1;
for(int i = 0; i < queries; i++)
{
int ans = 0;
for(int j = 0; j < n; j++)
{
int u = 2 * j;
if(idCycle[u] == idCycle[p])
{
if(idP != -1)
{
int dist = depth[u];
u = parCycle[u];
if((idInCycle[u] + g[i] - dist) % quantity[idCycle[p]] == idP) ans++;//printf("C1 %d\n", u);
}
else
if(parCycle[u] == parCycle[p] && depth[u] - depth[p] == g[i]) ans++;// printf("C3 %d\n", u);
}
if(idCycle[u] == idCycle[p + 1])
{
if(idP2 != -1)
{
int dist = depth[u];
u = parCycle[u];
if((idInCycle[u] + g[i] - dist) % quantity[idCycle[p + 1]] == idP2) ans++;// printf("C2 %d\n", u);
}
else
if(parCycle[u] == parCycle[p + 1] && depth[u] - depth[p + 1] == g[i])ans++;// printf("C4 %d\n", u);
}
}
answer(ans);
// printf("%d ", ans);
}
// printf("\n");
}
/*
int main ()
{
scanf("%d %d %d", &N, &M, &P);
for(int i = 0; i < M; i++)
scanf("%d %d", &R[i][0], &R[i][1]);
scanf("%d", &Q);
for(int i = 0; i < Q; i++) scanf("%d", &G[i]);
count_routes(N, M, P, R, Q, G);
}
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
7552 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
7552 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
7552 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
