Submission #883407

#TimeUsernameProblemLanguageResultExecution timeMemory
883407serifefedartarRegions (IOI09_regions)C++17
100 / 100
4125 ms49512 KiB
#include <bits/stdc++.h> using namespace std; #define fast ios::sync_with_stdio(0);cin.tie(0); #define s second #define f first typedef long long ll; const ll MOD = 1e9 + 9; const ll LOGN = 21; const ll MAXN = 2e5 + 100; vector<vector<int>> graph; int reg[MAXN], dp[505][505]; vector<int> cnt[MAXN], Rin[25100], Rout[25100], plc[25100]; map<pair<int,int>, pair<int,bool>> memo; void dfs(int node, int parent) { cnt[node][reg[node]]++; for (int reg_other = 1; reg_other <= 500; reg_other++) dp[reg_other][reg[node]] += cnt[node][reg_other]; for (auto u : graph[node]) { swap(cnt[u], cnt[node]); dfs(u, node); } cnt[node][reg[node]]--; swap(cnt[parent], cnt[node]); } int T = 0; int tin[MAXN], tout[MAXN]; void dfs2(int node, int parent) { tin[node] = ++T; Rin[reg[node]].push_back(tin[node]); for (auto u : graph[node]) dfs2(u, node); tout[node] = ++T; Rout[reg[node]].push_back(tout[node]); } int main() { fast int N, R, Q, a, b; cin >> N >> R >> Q; graph = vector<vector<int>>(N+1, vector<int>()); cin >> reg[1]; plc[reg[1]].push_back(1); for (int i = 2; i <= N; i++) { int S; cin >> S >> reg[i]; plc[reg[i]].push_back(i); graph[S].push_back(i); } if (R <= 500) { cnt[1] = vector<int>(505, 0); dfs(1, 1); for (int i = 0; i < Q; i++) { cin >> a >> b; cout << dp[a][b] << endl; } } else { dfs2(1, 1); for (int i = 1; i <= R; i++) { sort(Rin[i].begin(), Rin[i].end()); sort(Rout[i].begin(), Rout[i].end()); } for (int i = 0; i < Q; i++) { cin >> a >> b; if (memo[{a, b}].s == false) { int ans = 0; if (plc[a].size() < plc[b].size()) for (auto u : plc[a]) ans += (upper_bound(Rin[b].begin(), Rin[b].end(), tout[u]) - Rin[b].begin()) - (upper_bound(Rin[b].begin(), Rin[b].end(), tin[u]) - Rin[b].begin()); else for (auto u : plc[b]) ans += (upper_bound(Rin[a].begin(), Rin[a].end(), tin[u]) - Rin[a].begin()) - (upper_bound(Rout[a].begin(), Rout[a].end(), tin[u]) - Rout[a].begin()); memo[{a, b}] = {ans, 1}; } cout << memo[{a, b}].f << endl; } } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...