Submission #1071837

#TimeUsernameProblemLanguageResultExecution timeMemory
1071837ArthuroWichRegions (IOI09_regions)C++17
45 / 100
8095 ms29816 KiB
#include <bits/stdc++.h> using namespace std; #define int long long int vector<int> adj[300005], reg[25005]; int st[300005], en[300005], timer = 0; void dfs(int i, int p) { st[i] = timer; timer++; for (int j : adj[i]) { if (j == p) { continue; } dfs(j, i); } en[i] = timer; } void solve() { int n, r, q; cin >> n >> r >> q; for (int i = 1; i <= n; i++) { int s, h; if (i == 1) { cin >> h; reg[h].push_back(i); } else { cin >> s >> h; reg[h].push_back(i); adj[s].push_back(i); adj[i].push_back(s); } } dfs(1, -1); while(q--) { int a, b, ans = 0; cin >> a >> b; for (int i : reg[a]) { for (int j : reg[b]) { if (st[i] < st[j] && st[j] < en[i]) { ans++; } } } cout << ans << endl; } } int32_t main() { ios::sync_with_stdio(0); cin.tie(0); int t; t = 1; while(t--) { solve(); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...