제출 #895393

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
895393		ilef	Regions (IOI09_regions)	C++14	15 / 100	8080 ms	17236 KiB

regions

#include <bits/stdc++.h>
using namespace std;
const int N=250001;
const int R=501;
int H[N];
vector<int>graph[N];
vector<int>v[R];
int in[N];
int ot[N];
int timer = 0;
void dfs(int v , int p ) {
	in[v] = timer++;
	for (int x : graph[v]) {
		if (x == p) continue;
		dfs(x, v);
	}
	ot[v] = timer++;
}
 
 
bool anc(int u, int v) { return (in[u] <= in[v] && ot[u] >= ot[v]); }
 
int main() {
 
	int n,r,q;
	cin >> n >>r >> q;
	cin>>H[0];
    H[0]--;
    v[H[0]].push_back(0);
    for(int i=1;i<=n-1;i++){
        int u;
        cin>>u>>H[i];
        H[i]--;
        u--;
        v[H[i]].push_back(i);
        graph[u].push_back(i);
        graph[i].push_back(u);
    }
       
        dfs(0,-1);
       while(q--){
           int r1,r2;
           cin>>r1>>r2;
           //cout<<endl;
           
           r1--;r2--;
           int cnt=0;
           for(auto u:v[r1]){
               for(auto w:v[r2]){
                   if(anc(u,w)==true){
                       cnt++;
                   }
               }
           }
           cout<<cnt<<endl;
              
       }
	
}

• Subtask 1: 15 / 15
• Subtask 2: 0 / 85