Submission #1201991

#TimeUsernameProblemLanguageResultExecution timeMemory
1201991NikoBaoticRegions (IOI09_regions)C++20
30 / 100
372 ms25548 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 R = 510; int n, r, q; int h[N]; int par[N]; vector<int> chi[N]; int in[N]; int out[N]; int timer; int cnt[R][R]; vector<int>* dfs(int node) { timer++; in[node] = timer; 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 < R; i++) { (*cur)[i] += (*v)[i]; } delete(v); } } if (sz(chi[node]) == 0) { cur = new vector<int>(R); } for (int i = 1; i < R; i++) { cnt[h[node]][i] += (*cur)[i]; } (*cur)[h[node]]++; out[node] = timer; return cur; } 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]; } dfs(1); for (int i = 0; i < q; i++) { int r1, r2; cin >> r1 >> r2; int ans = cnt[r1][r2]; cout << ans << endl; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...