제출 #1135786

#제출 시각아이디문제언어결과실행 시간메모리
1135786m_bezrutchkaRegions (IOI09_regions)C++20
100 / 100
2751 ms49804 KiB
#include <bits/stdc++.h> using namespace std; #define int long long const int MAXN = 2e5 + 10; const int SQRT = 512; vector<int> adj[MAXN]; int n, r, q; int cnt[SQRT]; int tot[SQRT][SQRT], reg[MAXN], sup[MAXN]; int id_large[MAXN]; vector <int> large; vector<int> pos[MAXN], vals[MAXN], pos2[MAXN]; int tin[MAXN], tout[MAXN], tcur; void dfs_sub_1(int v) { int rid = id_large[reg[v]]; if (rid) { for (int i = 1; i < (int) large.size(); i++) { tot[i][rid] += cnt[i]; } cnt[rid]++; } for (int w: adj[v]) { dfs_sub_1(w); } if (rid) { cnt[rid]--; } } void dfs_sub_2(int v) { tin[v] = ++tcur; pos[reg[v]].push_back(tin[v]); vals[reg[v]].push_back(v); for (int w: adj[v]) { dfs_sub_2(w); } tout[v] = tcur; pos2[reg[v]].push_back(tout[v]); } int query(int l, int r, int x) { auto it_l = lower_bound(pos[x].begin(), pos[x].end(), l); auto it_r = upper_bound(pos[x].begin(), pos[x].end(), r); return it_r - it_l; } int query_inv(int i, int x) { int it_l = upper_bound(pos[x].begin(), pos[x].end(), i) - pos[x].begin(); int it_r = lower_bound(pos2[x].begin(), pos2[x].end(), i) - pos2[x].begin(); return it_l - it_r; } void solve() { large.push_back(0); cin >> n >> r >> q; cin >> reg[1]; for (int i = 2; i <= n; i++) { cin >> sup[i] >> reg[i]; adj[sup[i]].push_back(i); } dfs_sub_2(1); for (int i = 1; i <= r; i++) { sort(pos2[i].begin(), pos2[i].end()); } for (int i = 1; i <= r; i++) { if ((int) vals[i].size() > 500) { id_large[i] = large.size(); large.push_back(i); } } dfs_sub_1(1); while (q--) { int x, y; cin >> x >> y; int resp = 0; if (!id_large[x]) { for (int v: vals[x]) { resp += query(tin[v], tout[v], y); } } else if (!id_large[y]) { for (int v: vals[y]) { resp += query_inv(tin[v], x); } } else { resp = tot[id_large[x]][id_large[y]]; } cout << resp << endl; } } int32_t main() { ios_base::sync_with_stdio(false); cin.tie(0); solve(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...