# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1248798 | cpismylifeOwO | Tropical Garden (IOI11_garden) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
const long long mod = 1e9 + 7;
const int MaxN = 1e6 + 5;
int n1, m1, p1, q1;
int eg[MaxN][2];
int qy[MaxN];
#ifdef cpismylifeOwO
void Inp()
{
cin >> n1 >> m1 >> p1;
for (int x = 0; x < m1; x++)
{
cin >> eg[x][0] >> eg[x][1];
}
cin >> q1;
for (int x = 0; x < q1; x++)
{
cin >> qy[x];
}
}
void Answer(int u)
{
cout << u << "\n";
}
#endif // cpismylifeOwO
int n, m, p, q;
pair<int, int> edges[MaxN];
vector<int> graph[MaxN];
int query[MaxN];
int nxt[MaxN];
bool visited[MaxN];
pair<int, int> now[2][MaxN];
void DFS(int u, int p, int id)
{
if (visited[u] || nxt[u] == 0)
{
return;
}
DFS(nxt[u], p, id);
if (~now[id][nxt[u]].first)
{
now[id][u] = now[id][nxt[u]];
now[id][u].second++;
}
if (u == p)
{
now[id][u] = make_pair(0, 0);
}
visited[u] = true;
//cout << u << ":" << now[id][u].first << ":" << now[id][u].second << "\n";
}
void Calc(int p, int id)
{
for (int x = 1; x <= 2 * n; x++)
{
now[id][x] = make_pair(-1, -1);
visited[x] = false;
}
for (int x = 1; x <= 2 * n; x++)
{
if (!visited[x])
{
int h = x, t = x;
bool vis = false;
do
{
if (nxt[h] == 0 || nxt[nxt[h]] == 0)
{
vis = true;
break;
}
if (visited[h] || visited[t])
{
vis = true;
break;
}
h = nxt[nxt[h]];
t = nxt[t];
}
while (h != t);
if (!vis)
{
int a = x, cnt = 0;
while (a != t)
{
a = nxt[a];
t = nxt[t];
}
bool isthere = (t == p);
do
{
a = nxt[a];
if (a == p)
{
isthere = true;
}
cnt++;
}
while (a != t);
if (isthere)
{
while (a != p)
{
a = nxt[a];
}
now[id][a] = make_pair(cnt, 0);
visited[a] = true;
int t = a;
a = nxt[a];
now[id][a] = make_pair(cnt, cnt - 1);
visited[a] = true;
while (t != a)
{
now[id][nxt[a]] = make_pair(now[id][a].first, now[id][a].second - 1);
a = nxt[a];
visited[a] = true;
}
}
else
{
visited[t] = true;
a = nxt[a];
while (a != t)
{
visited[a] = true;
a = nxt[a];
}
}
}
DFS(x, p, id);
}
}
}
void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
n = N;
m = M;
p = P + 1;
q = Q;
for (int x = 1; x <= m; x++)
{
edges[x] = make_pair(R[x - 1][0] + 1, R[x - 1][1] + 1);
graph[edges[x].first].push_back(edges[x].second);
graph[edges[x].second].push_back(edges[x].first);
}
for (int x = 1; x <= q; x++)
{
query[x] = G[x - 1];
}
for (int x = 1; x <= n; x++)
{
if (graph[graph[x][0]].size() == 1 || graph[graph[x][0]][0] != x)
{
nxt[x] = graph[x][0];
}
else
{
nxt[x] = graph[x][0] + n;
}
if (graph[x].size() > 1)
{
if (graph[graph[x][1]].size() == 1 || graph[graph[x][1]][0] != x)
{
nxt[x + n] = graph[x][1];
}
else
{
nxt[x + n] = graph[x][1] + n;
}
}
}
Calc(p, 0);
Calc(p + n, 1);
for (int x = 1; x <= q; x++)
{
int cnt = 0;
for (int y = 1; y <= n; y++)
{
cnt += ((((~now[0][y].first) && (query[x] >= now[0][y].second) && now[0][y].first > 0 && (query[x] - now[0][y].second) % now[0][y].first == 0) ||
(now[0][y].first == 0 && query[x] == now[0][y].second)) ||
(((~now[1][y].first) && (query[x] >= now[1][y].second) && now[1][y].first > 0 && (query[x] - now[1][y].second) % now[1][y].first == 0)
|| (now[1][y].first == 0 && query[x] == now[1][y].second)));
}
Answer(cnt);
}
}
#ifdef cpismylifeOwO
void Exc()
{
count_routes(n1, m1, p1, eg, q1, qy);
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int test = 1;
//cin >> test;
for (int x = 1; x <= test; x++)
{
Inp();
Exc();
}
return 0;
}
#endif // cpismylifeOwO