Submission #1202015

#TimeUsernameProblemLanguageResultExecution timeMemory
1202015NikoBaoticRegions (IOI09_regions)C++20
30 / 100
8093 ms21380 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 BIT[N]; void updateAt(int ind, int delta) { for (int i = ind + 1; ind < N; i += i&-i) { BIT[ind] += delta; } } ll query(int ind) { ll sum = 0; for (int i = ind + 1; ind > 0; i -= i&-i) { sum += BIT[i]; } return sum; } void update(int l, int r, int delta) { updateAt(l, delta); updateAt(r + 1, delta); } 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]); } 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...