oj.uz

Submission #895387

# Submission time Handle Problem Language Result Execution time Memory
895387 2023-12-29T20:59:18 Z ilef Regions (IOI09_regions) C++14
8 / 100
 19 ms 856 KB 
#include <bits/stdc++.h>
#define MAXN 100005
#define bitinc(x) (x & -x);
using namespace std;
const int N=2501;
const int R=501;
int H[N];
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--;
           int cnt=0;
           for(auto u:v[r1]){
               for(auto w:v[r2]){
                   if(anc(u,w)==true){
                       cnt++;
                   }
               }
           }
           cout<<cnt<<endl;
       }
	
}

Subtask #1
8.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 756 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 3 ms 344 KB Output is correct
5 Correct 4 ms 344 KB Output is correct
6 Correct 10 ms 344 KB Output is correct
7 Correct 16 ms 344 KB Output is correct
8 Correct 19 ms 600 KB Output is correct
9 Runtime error 2 ms 856 KB Execution killed with signal 11
10 Runtime error 2 ms 856 KB Execution killed with signal 11
11 Runtime error 2 ms 856 KB Execution killed with signal 11
12 Runtime error 2 ms 856 KB Execution killed with signal 11
13 Runtime error 2 ms 856 KB Execution killed with signal 11
14 Runtime error 2 ms 856 KB Execution killed with signal 11
15 Runtime error 2 ms 856 KB Execution killed with signal 11

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 856 KB Execution killed with signal 11
2 Runtime error 2 ms 856 KB Execution killed with signal 11
3 Runtime error 2 ms 856 KB Execution killed with signal 11
4 Runtime error 1 ms 600 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 1 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 1 ms 600 KB Execution killed with signal 11
15 Runtime error 1 ms 600 KB Execution killed with signal 11
16 Runtime error 1 ms 852 KB Execution killed with signal 11
17 Runtime error 1 ms 600 KB Execution killed with signal 11