제출 #1189304

#제출 시각아이디문제언어결과실행 시간메모리
1189304akamizaneRegions (IOI09_regions)C++20
0 / 100
36 ms16428 KiB
#include<bits/stdc++.h> using namespace std; #define debug(...) 42 #define int long long using ll = long long; const int maxn = 2e5 + 1; vector<int> ad[maxn], comp[25001]; int tin[maxn], tout[maxn], ord[maxn], a[25001], id[25001], timeDfs = 0; vector<vector<int>> calc; void tour(int u){ tin[u] = timeDfs++; ord[tin[u]] = u; comp[a[u]].push_back(tin[u]); for (auto v : ad[u]) tour(v); tout[u] = timeDfs; } void dfs(int u, int par_reg, int par_cnt){ if (a[u] == par_reg) par_cnt++; calc[id[par_reg]][a[u]] += par_cnt; for (auto v : ad[u]) dfs(v, par_reg, par_cnt); } void solve(){ int n, r, q; cin >> n >> r >> q; cin >> a[0]; a[0]--; for (int i = 1; i < n; i++){ int p, h; cin >> p >> h; p--; h--; ad[p].push_back(i); a[i] = h; } for (int i = 0; i < r; i++) id[i] = -1; tour(0); int cur = 0; const int block = sqrt(n); for (int i = 0; i < r; i++){ if (comp[i].size() >= block){ id[i] = cur++; calc.push_back(vector<int> (r)); dfs(0, i, 0); } } while(q--){ int e1, e2; cin >> e1 >> e2; e1--, e2--; if (comp[e1].size() >= block){ cout << calc[id[e1]][e2] << "\n"; } else{ int ans = 0; for (auto u : comp[e1]){ ans += lower_bound(comp[e2].begin(), comp[e2].end(), tout[ord[u]]) - lower_bound(comp[e2].begin(), comp[e2].end(), tin[ord[u]]); } cout << ans << "\n"; } } } int32_t main() { ios_base::sync_with_stdio(false); cin.tie(0); int tt = 1; // cin >> tt; while(tt--) { solve(); } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...