Submission #1202010

#TimeUsernameProblemLanguageResultExecution timeMemory
1202010NikoBaoticRegions (IOI09_regions)C++20
40 / 100
8093 ms24464 KiB
#include "bits/stdc++.h" using namespace std; typedef long long ll; typedef pair<ll, ll> pii; #define all(x) x.begin(), x.end() #define sz(x) ((int) ((x).size())) #define pb push_back #define F first #define S second #define FIO ios_base::sync_with_stdio(false); cin.tie(0) const int N = 200100; const int R1 = 510; const int R2 = 25010; const int off = 1 << 18; int tr[off * 4]; int lazy[off * 4]; void prop(int node, int x, int y) { tr[node] += lazy[node]; if (x != y) { lazy[node * 2] += lazy[node]; lazy[node * 2 + 1] += lazy[node]; } lazy[node] = 0; } void update(int l, int r, int delta, int node = 1, int x = 0, int y = off - 1) { if (x > r or y < l) return; if (l <= x and y <= r) { lazy[node] += delta; prop(node, x, y); return; } prop(node, x, y); update(l, r, delta, node * 2, x, (x + y) / 2); update(l, r, delta, node * 2 + 1, (x + y) / 2 + 1, y); tr[node] = tr[node * 2] + tr[node * 2 + 1]; } int query(int l, int r, int node = 1, int x = 0, int y = off - 1) { if (x > r or y < l) return 0; prop(node, x, y); if (l <= x and y <= r) return tr[node]; return query(l, r, node * 2, x, (x + y) / 2) + query(l, r, node * 2 + 1, (x + y) / 2 + 1, y); } int n, r, q; int h[N]; int par[N]; vector<int> chi[N]; vector<int> emp[R2]; int in[N]; int out[N]; int timer; int cnt[R1][R1]; vector<int>* dfs(int node) { vector<int>* cur = nullptr; for (int u : chi[node]) { vector<int>* v = dfs(u); if (cur == nullptr) { cur = v; } else { for (int i = 1; i < R1; i++) { (*cur)[i] += (*v)[i]; } delete(v); } } if (sz(chi[node]) == 0) { cur = new vector<int>(R1); } for (int i = 1; i < R1; i++) { cnt[h[node]][i] += (*cur)[i]; } (*cur)[h[node]]++; return cur; } void dfs2(int node) { timer++; in[node] = timer; for (int u : chi[node]) { dfs2(u); } out[node] = timer; } int main() { FIO; cin >> n >> r >> q; for (int i = 1; i <= n; i++) { if (i != 1) { cin >> par[i]; chi[par[i]].pb(i); } cin >> h[i]; emp[h[i]].pb(i); } if (r <= 500) { dfs(1); for (int i = 0; i < q; i++) { int r1, r2; cin >> r1 >> r2; int ans = cnt[r1][r2]; cout << ans << endl; } } else { dfs2(1); for (int i = 0; i < q; i++) { int r1, r2; cin >> r1 >> r2; for (int x : emp[r1]) { update(in[x], out[x], 1); } int ans = 0; for (int x : emp[r2]) { ans += query(in[x], in[x]); } for (int x : emp[r1]) { update(in[x], out[x], -1); } cout << ans << endl; } } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...