제출 #909105

#제출 시각아이디문제언어결과실행 시간메모리
909105anarch_yRegions (IOI09_regions)C++17
45 / 100
8086 ms23672 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; #define all(x) begin(x), end(x) #define sz(x) (int)x.size() #define pb push_back const int maxn = 200001; vector<int> adj[maxn]; int st[maxn], en[maxn]; int timer = 0; void dfs(int s, int p){ st[s] = timer++; for(auto u: adj[s]){ if(u == p) continue; dfs(u, s); } en[s] = timer; } bool anc(int a, int b){ return st[a] <= st[b] and en[b] <= en[a]; } int main(){ ios::sync_with_stdio(0); cin.tie(0); int N, R, Q; cin >> N >> R >> Q; vector<int> reg[R+1]; int h; cin >> h; reg[h].pb(1); for(int i=2; i<=N; i++){ int p, r; cin >> p >> r; adj[i].pb(p); adj[p].pb(i); reg[r].pb(i); } dfs(1, 0); while(Q--){ int r1, r2; cin >> r1 >> r2; int ans = 0; for(auto a: reg[r1]){ for(auto b: reg[r2]){ if(anc(a, b)) ans++; } } cout << ans << "\n"; cout.flush(); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...