제출 #1205765

#제출 시각아이디문제언어결과실행 시간메모리
1205765shangkueiTropical Garden (IOI11_garden)C++20
0 / 100
1 ms576 KiB
#include "garden.h" #include <bits/stdc++.h> #include "gardenlib.h" using namespace std; void count_routes(int N, int M, int P, int R[][2], int Q, 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 < N; i++) { if (ideg[i] == 0 || floydC[i] == -1) floyd(i); } auto dist = [&](int u) { vector<int> dist(2 * N, -1); queue<int> q; dist[u] = 0; q.push(u); 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++; } answer(cnt); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...