//#include "gardenlib.h"
#include "garden.h"
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
const int N = 1.5e5+10, inf = 2e9;
int dis[N][2], cycle[N][2];
vector<int> G[2 * N];
bool seen[2 * N][2];
int par[2 * N][2];
bool check(int v, int d)
{
bool ans = false;
if(dis[v][0] != inf)
if(dis[v][0] <= d)
{
int x = d - dis[v][0];
if(x % cycle[v][0] == 0)
return true;
}
if(dis[v][1] != inf)
if(dis[v][1] <= d)
{
int x = d - dis[v][1];
if(x % cycle[v][1] == 0)
return true;
}
return false;
}
void update_cycle(int v, int c)
{
int d = dis[v][c] + 1;
while(v != -1)
{
//cerr << "Cycle : " << v << ' ' << c << endl;
cycle[v][c] = d;
v = par[v][c];
}
}
void bfs(int v, int n2, int c) // n2 = 2 * n
{
for(int i = 0; i < n2; i++)
dis[i][c] = cycle[i][c] = inf, par[i][c] = -1;
queue<int> Q;
Q.push(v);
seen[v][c] = true;
dis[v][c] = 0;
while(Q.size())
{
int ver = Q.front();
Q.pop();
for(int u : G[ver])
{
if(u == v) update_cycle(u, c);
if(seen[u][c]) continue;
Q.push(u);
seen[u][c] = true;
par[u][c] = ver;
dis[u][c] = dis[ver][c] + 1;
}
}
}
void count_routes(int n, int m, int e, int edge[][2], int q, int k[])
{
int cnt[n] = {}, c[n] = {};
for(int i = 0; i < m ;i++)
c[edge[i][0]]++, c[edge[i][1]]++;
for(int i = 0; i < m; i++)
{
int u = edge[i][0], v = edge[i][1];
cnt[u]++, cnt[v]++;
if(cnt[u] == 1)
{
if((cnt[v] == 1 && c[v] == 1) || (cnt[v] > 1))
G[v].pb(u);
else
G[v + n].pb(u);
}
if(cnt[u] == 2)
{
if((cnt[v] == 1 && c[v] == 1) || (cnt[v] > 1))
G[v].pb(u + n);
else
G[v + n].pb(u + n);
}
if(cnt[v] == 1)
{
if((cnt[u] == 1 && c[u] == 1) || (cnt[u] > 1))
G[u].pb(v);
else
G[u + n].pb(v);
}
if(cnt[v] == 2)
{
if((cnt[u] == 1 && c[u] == 1) || (cnt[u] > 1))
G[u].pb(v + n);
else
G[u + n].pb(v + n);
}
}
bfs(e, 2 * n, 0);
bfs(e + n, 2 * n, 1);
for(int i = 0; i < q; i++)
{
int ans = 0;
for(int v = 0; v < n; v++)
ans += check(v, k[i]);
//answer(ans);
cout << ans << ' ';
}
}
/*
#define MAX_M 1000000
#define MAX_Q 2000
static int NN, M, P, Q;
static int R[MAX_M][2];
static int g[MAX_Q];
void read_input()
{
int i;
scanf("%d %d %d",&NN,&M,&P);
for(i=0; i<M; i++)
scanf("%d %d",&R[i][0],&R[i][1]);
scanf("%d",&Q);
for(i=0; i<Q; i++)
scanf("%d",&g[i]);
}
void answer(int x)
{
printf("%d ", x);
}
int main()
{
read_input();
count_routes(NN,M,P,R,Q,g);
return 0;
}
//*/
Compilation message
garden.cpp: In function 'bool check(int, int)':
garden.cpp:16:8: warning: unused variable 'ans' [-Wunused-variable]
16 | bool ans = false;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
10588 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
10588 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
10588 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
