Submission #895388

#	Time	Username	Problem	Language	Result	Execution time	Memory
895388		ilef	Regions (IOI09_regions)	C++14	5 / 100	4 ms	4776 KiB

regions

#include <bits/stdc++.h>
using namespace std;
const int N=501;
const int R=501;
int H[N];
map<pair<int,int>,int>mp;
vector<int>graph[N];
vector<int>v[R];
int id[N];
int sz[N];
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--;
           if(!mp.count({r1,r2})){
           int cnt=0;
           for(auto u:v[r1]){
               for(auto w:v[r2]){
                   if(anc(u,w)==true){
                       cnt++;
                   }
               }
           }
           cout<<cnt<<endl;
               mp[{r1,r2}]=cnt;
           }
           else{
               cout<<mp[{r1,r2}]<<endl;
           }
       }
	
}

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