Submission #1213498

#TimeUsernameProblemLanguageResultExecution timeMemory
1213498vaneaRegions (IOI09_regions)C++20
15 / 100
482 ms196608 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; const int mxN = 2e5+10; const int mxR = 5e2+10; int reg[mxN]; vector<int> adj[mxN]; int ans[mxR][mxR]; int dp[mxN][mxR]; void dfs(int node, int p) { dp[node][reg[node]]++; for(auto it : adj[node]) { if(it == p) continue; dfs(it, node); for(int i = 1; i <= 500; i++) { dp[node][i] += dp[it][i]; } } for(int i = 1; i <= 500; i++) { ans[reg[node]][i] += dp[node][i]; } } int main() { ios_base::sync_with_stdio(0); cin.tie(0); int n, r, q; cin >> n >> r >> q; cin >> reg[1]; for(int i = 2; i <= n; i++) { int p; cin >> p >> reg[i]; adj[p].push_back(i); adj[i].push_back(p); } dfs(1, 0); while(q--) { int r1, r2; cin >> r1 >> r2; cout << ans[r1][r2] << '\n'; cout.flush(); } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...