Submission #1086488

#TimeUsernameProblemLanguageResultExecution timeMemory
10864880x34cRegions (IOI09_regions)C++17
33 / 100
2723 ms40916 KiB
#include <bits/stdc++.h> #define ll long long #define pii pair<int, int> #define int ll using namespace std; int N, R, Q, SQRT_N; vector<vector<int>> graph, sol, rgraph; vector<int> regions, reg_cnt, sqrt_r, conv, tin, tout; vector<int> cnt; void dfs(int v) { for (int r : sqrt_r) sol[conv[r]][regions[v]] += cnt[conv[r]]; cnt[regions[v]]++; for (int u : graph[v]) dfs(u); cnt[regions[v]]--; } void etour(int v, int &tim) { rgraph[regions[v]].push_back(v); tin[v] = tim++; for (int u : graph[v]) etour(u, tim); tout[v] = tim++; } signed main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> N >> R >> Q; SQRT_N = sqrt(N); graph = vector<vector<int>>(N); regions = vector<int>(N, -1); reg_cnt = vector<int>(R, 0); conv = vector<int>(R, -1); cnt = vector<int>(R, 0); tin = vector<int>(N); tout = vector<int>(N); rgraph = vector<vector<int>>(R); cin >> regions[0]; --regions[0]; reg_cnt[regions[0]]++; for (int i = 1; i < N; i++) { int v; cin >> v >> regions[i]; --regions[i]; --v; graph[v].push_back(i); reg_cnt[regions[i]]++; } for (int i = 0; i < R; i++) if (reg_cnt[i] > SQRT_N) { sqrt_r.push_back(i); conv[i] = sqrt_r.size() - 1; } if (!sqrt_r.empty()) sol = vector<vector<int>>(sqrt_r.size(), vector<int>(R, 0)); int tim = 0; etour(0, tim); dfs(0); while (Q--) { int a, b; cin >> a >> b; --a; --b; if (conv[a] != -1) { cout << sol[conv[a]][b] << endl; continue; } int res = 0; for (int v : rgraph[a]) { if (rgraph[b].empty()) continue; int l = 0, r = rgraph[b].size() - 1; int lb = -1; while (l <= r) { int m = l + (r - l) / 2; int u = rgraph[b][m]; if (tin[u] < tin[v]) l = m + 1; else if (tout[u] > tout[v]) r = m - 1; else { lb = m; r = m - 1; } } if (lb == -1) continue; l = 0; r = rgraph[b].size() - 1; int rb = -1; while (l <= r) { int m = l + (r - l) / 2; int u = rgraph[b][m]; if (tin[u] < tin[v]) l = m + 1; else if (tout[u] > tout[v]) r = m - 1; else { rb = m; l = m + 1; } } res += (rb - lb + 1); } cout << res << endl; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...