oj.uz

답안 #895388

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
895388 2023-12-29T21:02:00 Z ilef Regions (IOI09_regions) C++14
5 / 100
 4 ms 4776 KB 
#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.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 2 ms 484 KB Output is correct
5 Correct 4 ms 752 KB Output is correct
6 Runtime error 3 ms 4776 KB Execution killed with signal 11
7 Runtime error 2 ms 4696 KB Execution killed with signal 11
8 Runtime error 3 ms 4696 KB Execution killed with signal 11
9 Runtime error 3 ms 4604 KB Execution killed with signal 11
10 Runtime error 3 ms 4696 KB Execution killed with signal 11
11 Runtime error 3 ms 4696 KB Execution killed with signal 11
12 Runtime error 3 ms 4696 KB Execution killed with signal 11
13 Runtime error 4 ms 4696 KB Execution killed with signal 11
14 Runtime error 3 ms 4696 KB Execution killed with signal 11
15 Runtime error 3 ms 4696 KB Execution killed with signal 11

Subtask #2
0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 3 ms 4696 KB Execution killed with signal 11
2 Runtime error 3 ms 4696 KB Execution killed with signal 11
3 Runtime error 3 ms 4696 KB Execution killed with signal 11
4 Runtime error 1 ms 760 KB Execution killed with signal 11
5 Runtime error 1 ms 600 KB Execution killed with signal 11
6 Runtime error 1 ms 600 KB Execution killed with signal 11
7 Runtime error 1 ms 600 KB Execution killed with signal 11
8 Runtime error 1 ms 600 KB Execution killed with signal 11
9 Runtime error 0 ms 600 KB Execution killed with signal 11
10 Runtime error 1 ms 600 KB Execution killed with signal 11
11 Runtime error 1 ms 600 KB Execution killed with signal 11
12 Runtime error 1 ms 600 KB Execution killed with signal 11
13 Runtime error 1 ms 600 KB Execution killed with signal 11
14 Runtime error 0 ms 600 KB Execution killed with signal 11
15 Runtime error 1 ms 600 KB Execution killed with signal 11
16 Runtime error 0 ms 600 KB Execution killed with signal 11
17 Runtime error 1 ms 596 KB Execution killed with signal 11