Submission #1213506

#TimeUsernameProblemLanguageResultExecution timeMemory
1213506vaneaRegions (IOI09_regions)C++20
35 / 100
8093 ms26820 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; const int mxN = 2e5+10; const int mxR = 3e4+10; int reg[mxN], st[4*mxN]; vector<int> adj[mxN], emp[mxR]; int tin[mxN], tout[mxN], timer = -1; void dfs(int node, int p) { tin[node] = ++timer; for(auto it : adj[node]) { if(it == p) continue; dfs(it, node); } tout[node] = timer; } void upd(int node, int l, int r, int k, int x) { if(l == r && l == k) { st[node] = x; return ; } if(l > k || r < k) return ; int mid = (l+r)/2; upd(node*2, l, mid, k, x); upd(node*2+1, mid+1, r, k, x); st[node] = st[node*2] + st[node*2+1]; } int qry(int node, int l, int r, int l1, int r1) { if(l1 <= l && r <= r1) return st[node]; if(l1 > r || r1 < l) return 0; int mid = (l+r)/2; return qry(node*2, l, mid, l1, r1) + qry(node*2+1, mid+1, r, l1, r1); } int main() { ios_base::sync_with_stdio(0); cin.tie(0); int n, r, q; cin >> n >> r >> q; cin >> reg[1]; emp[reg[1]].push_back(1); for(int i = 2; i <= n; i++) { int p; cin >> p >> reg[i]; emp[reg[i]].push_back(i); adj[p].push_back(i); adj[i].push_back(p); } dfs(1, 0); while(q--) { int r1, r2; cin >> r1 >> r2; int ans = 0; for(auto it : emp[r2]) { upd(1, 0, timer+1, tin[it], 1); } for(auto it : emp[r1]) { ans += qry(1, 0, timer+1, tin[it], tout[it]); } for(auto it : emp[r2]) { upd(1, 0, timer+1, tin[it], 0); } cout << ans << '\n'; cout.flush(); } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...