제출 #1189315

#제출 시각아이디문제언어결과실행 시간메모리
1189315akamizaneRegions (IOI09_regions)C++17
0 / 100
357 ms34680 KiB
#include<bits/stdc++.h> using namespace std; #ifdef LOCAL #include <debug.h> #else #define debug(...) 42 #endif void solve(){ int n, r, q; cin >> n >> r >> q; int timeDfs = 0; vector<int> a, tin, tout, ord, id; vector<vector<int>> calc, ad, comp; a.resize(n); ad.resize(n); tin.resize(n); tout.resize(n); ord.resize(n); comp.resize(r); id.assign(r, -1); 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; function<void(int)> tour = [&](int u) -> void { tin[u] = timeDfs++; ord[tin[u]] = u; comp[a[u]].push_back(tin[u]); for (int v : ad[u]) { tour(v); } tout[u] = timeDfs; }; tour(0); int cur = 0; function<void(int, int, int)> dfs = [&](int u, int par_reg, int par_cnt) -> void { if (a[u] == par_reg) { par_cnt++; } calc[id[par_reg]][a[u]] += par_cnt; for (int v : ad[u]) { dfs(v, par_reg, par_cnt); } }; 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...