Submission #1097408

#TimeUsernameProblemLanguageResultExecution timeMemory
1097408VectorLiTropical Garden (IOI11_garden)C++17
69 / 100
5055 ms29168 KiB
#pragma GCC optimize(3) #pragma GCC target("avx") #pragma GCC optimize("Ofast") #include <bits/stdc++.h> #include "garden.h" #include "gardenlib.h" #define long long long using namespace std; const int V = (int) 1.5E5; int n, m, x; vector<pair<int, int>> e[V]; int t[V]; int p[V * 2]; int d[V * 2]; bitset<V * 2> f; vector<int> a[V * 2]; // int length[2]; int length[V * 2]; void generate() { queue<int> q; for (int i = 0; i < n * 2; i++) { if (d[i] == 0) { q.push(i); } } while (q.empty() == 0) { int u = q.front(), v = p[u]; q.pop(); f[u] = 1; d[v] = d[v] - 1; if (d[v] == 0) { q.push(v); } } for (int i = 0; i < n * 2; i++) { if (f[i] == 0) { vector<int> a; for (int u = i; f[u] == 0; u = p[u]) { a.push_back(u); f[u] = 1; } for (auto u : a) { length[u] = (int) a.size(); } } } } bitset<V * 2> state; int dist[V * 2]; void DFS(int u) { state[u] = 1; for (auto v : a[u]) { if (state[v] == 0) { dist[v] = dist[u] + 1; DFS(v); } } } int count(int u, int k) { state.reset(); fill(dist, dist + n * 2, (int) 1E9); dist[u] = 0; DFS(u); int sum = 0; for (int i = 0; i < n; i++) { if (length[u] == 0 && dist[i] == k) { sum = sum + 1; } if (length[u] > 0 && k - dist[i] >= 0 && (k - dist[i]) % length[u] == 0) { sum = sum + 1; } } return sum; } void count_routes(int N, int M, int P, int R[][2], int Q, int G[]) { n = N; m = M; x = P; fill(t, t + n, m); for (int i = 0; i < m; i++) { int u, v; u = R[i][0]; v = R[i][1]; e[u].push_back({v, i}); e[v].push_back({u, i}); t[u] = min(t[u], i); t[v] = min(t[v], i); } for (int u = 0; u < n; u++) { int v, i; tie(v, i) = e[u][0]; if (i != t[v]) { p[u] = v; d[v] = d[v] + 1; a[v].push_back(u); } else { p[u] = v + n; d[v + n] = d[v + n] + 1; a[v + n].push_back(u); } if ((int) e[u].size() > 1) { tie(v, i) = e[u][1]; } if (i != t[v]) { p[u + n] = v; d[v] = d[v] + 1; a[v].push_back(u + n); } else { p[u + n] = v + n; d[v + n] = d[v + n] + 1; a[v + n].push_back(u + n); } } generate(); int q = Q; for (int i = 0; i < q; i++) { int k = G[i]; answer(count(x, k) + count(x + n, k)); // cout << count(x, k) + count(x + n, k) << " "; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...