Submission #1086466

#TimeUsernameProblemLanguageResultExecution timeMemory
10864660x34cRegions (IOI09_regions)C++17
0 / 100
89 ms32848 KiB
#include <bits/stdc++.h> #define ll long long #define pii pair<int, int> #define endl '\n' using namespace std; int N, R, Q, SQRT_N; const int MAX_N = 2e5 + 1; const int MX_SQRT = 448; const int MAX_R = 25001; vector<int> graph[MAX_N], rgraph[MAX_N]; int sol[MX_SQRT][MAX_R]; int regions[MAX_N], reg_cnt[MAX_R], conv[MAX_R], tin[MAX_N], tout[MAX_N], cnt[MAX_R]; vector<int> sqrt_r; 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); 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; } else conv[i] = -1; } 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...