| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1205859 | shangkuei | Tropical Garden (IOI11_garden) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
inline namespace FileIO {
void setIn(string s) { (void)!freopen(s.c_str(), "r", stdin); }
void setOut(string s) { (void)!freopen(s.c_str(), "w", stdout); }
void setIO(string s = "") {
ios::sync_with_stdio(false);
cin.exceptions(cin.failbit); // throws exception when do something illegal
cin.tie(nullptr); // unsync C / C++ I/O streams
cout.tie(nullptr); // unsync C / C++ I/O streams
#ifndef SHANGKUEI
if (int(s.size())) setIn(s + ".in"), setOut(s + ".out"); // for old USACO
#endif
}
} // namespace FileIO
#define endl "\n"
#define space " "
// #define all(x) (x).begin(), (x).end()
// #define rall(x) (x).rbegin(), (x).rend()
// using ll = long long;
// using ul = unsigned long long;
using sz = size_t;
template <typename... Ts>
using V = vector<Ts...>;
// template <typename T1, typename T2> using P = pair<T1, T2>;
// template <typename T, sz N> using A = array<T, N>;
// template <typename... Ts> using D = deque<Ts...>;
// template <typename... Ts> using T = tuple<Ts...>;
// template <typename... Ts> using uS = unordered_set<Ts...>;
// template <typename... Ts> using S = set<Ts...>;
// template <typename... Ts> using uM = unordered_map<Ts...>;
// template <typename... Ts> using M = map<Ts...>;
// template <typename... Ts> using umM = unordered_multimap<Ts...>;
// template <typename... Ts> using mM = multimap<Ts...>;
// template <typename... Ts> using Q = queue<Ts...>;
// template <typename... Ts> using pQ = priority_queue<Ts...>;
class Solution {
public:
void Solve(int N, int M, int P, vector<vector<int>> R, int Q, vector<int> G) {
// build graph
vector<vector<int>> adj(N);
for (int i = 0; i < M; i++) {
adj[R[i][0]].push_back(R[i][1]);
adj[R[i][1]].push_back(R[i][0]);
}
auto node = [&](int p, int u) {
if (p == adj[u][0]) return N + u;
return u;
};
// build functional graph
vector<int> next(2 * N, -1), ideg(2 * N, 0);
vector<vector<int>> prev(2 * N);
auto connect = [&](int u, int v) {
ideg[v]++;
next[u] = v;
prev[v].push_back(u);
};
for (int i = 0; i < N; i++) {
connect(node(-1, i), node(i, adj[i][0]));
for (auto v : adj[i]) {
if (v != adj[i][0] || adj[i].size() == 1)
connect(node(v, i), node(i, adj[i][0]));
else
connect(node(v, i), node(i, adj[i][1]));
}
}
// t + c
vector<int> floydT(2 * N, -1), floydC(2 * N, -1);
auto floyd = [&](int u) {
int fast = u, slow = u;
int len = 0;
while (true) {
len++;
fast = next[next[fast]];
slow = next[slow];
if (fast == slow) break;
if (floydC[slow] != -1) break;
}
if (floydC[slow] != -1) {
fast = u;
for (int i = 0; i < len; i++) {
floydC[fast] = floydC[slow];
floydT[fast] = floydT[slow] + len - i;
fast = next[fast];
}
return;
}
int c = 0;
while (true) {
c++;
fast = next[fast];
if (fast == slow) break;
}
fast = u;
for (int i = 0; i < c; i++) {
floydC[slow] = c;
floydT[slow] = 0;
slow = next[slow];
fast = next[fast];
}
int t = 0;
slow = u;
while (true) {
t++;
slow = next[slow];
fast = next[fast];
if (fast == slow) break;
}
slow = u;
for (int i = 0; i < t; i++) {
floydC[slow] = c;
floydT[slow] = t - i;
slow = next[slow];
}
};
for (int i = 0; i < 2 * N; i++) {
if (ideg[i] == 0 || floydC[i] == -1) floyd(i);
}
auto dist = [&](int p) {
vector<int> dist(2 * N, -1);
queue<int> q;
dist[p] = 0;
q.push(p);
while (!q.empty()) {
int u = q.front();
q.pop();
for (int v : prev[u]) {
if (dist[v] == -1) {
dist[v] = dist[u] + 1;
q.push(v);
}
}
}
return dist;
};
auto reachable = [&](int u, int v, int k, const vector<int>& dist) {
if (dist[u] == -1) return false;
if (dist[u] == k) return true;
if (floydT[v] == 0 && k > dist[u] && (k - dist[u]) % floydC[v] == 0)
return true;
return false;
};
vector<int> distP = dist(P), distNP = dist(N + P);
for (int i = 0; i < Q; i++) {
int cnt = 0;
for (int j = 0; j < N; j++) {
if (reachable(j, P, G[i], distP) || reachable(j, N + P, G[i], distNP))
cnt++;
}
cout << cnt << endl;
}
}
};
int main() {
setIO();
Solution solve;
sz __ = 1ul;
for (auto _ = 0ul; _ < __; ++_) {
// input
int N, M, P;
cin >> N >> M >> P;
vector<vector<int>> R(M, vector<int>(2));
for (int i = 0; i < M; i++) cin >> R[i][0] >> R[i][1];
int Q;
cin >> Q;
vector<int> G(Q);
for (int i = 0; i < Q; i++) cin >> G[i];
// solve
solve.Solve(N, M, P, R, Q, G);
}
}