oj.uz

Submission #477607

# Submission time Handle Problem Language Result Execution time Memory
477607 2021-10-02T19:10:20 Z Abrar_Al_Samit Regions (IOI09_regions) C++17
0 / 100
 8000 ms 28520 KB 
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 5;
vector <int> g[maxn];
int H[maxn], ans, in[maxn], out[maxn], timer;
vector <int> reg[maxn];
void Euler(int v, int p ){
	in[v] = timer++;
	for(auto it : g[v]) if(it!=p) {
		Euler(it, v);
	}
	out[v] = timer++;
}
bool anc(int x, int y) {
	return in[x]<=in[y] && out[x]>=out[y];
}
int main() {
	int N, R, Q; cin >> N >> R >> Q;
	cin >> H[1];
	reg[H[1]].push_back(1);
	for(int i=2; i<=N; ++i) {
		int p; cin >> p >> H[i];
		g[p].push_back(i);
		g[i].push_back(p);
		reg[H[i]].push_back(i);
	}
	Euler(1, 1);
	while(Q--) {
		int r1, r2; cin >> r1 >> r2;
		int ans = 0;
		for(auto it : reg[r2]) {
			bool ok = false;
			for(auto it2 : reg[r1]) {
				ok |= anc(it2, it);
			}
			ans += ok;
		}
		cout << ans << endl;
	}
	return 0;
}

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 9672 KB Output isn't correct
2 Incorrect 5 ms 9672 KB Output isn't correct
3 Incorrect 6 ms 9672 KB Output isn't correct
4 Incorrect 10 ms 9672 KB Output isn't correct
5 Incorrect 13 ms 9672 KB Output isn't correct
6 Incorrect 19 ms 9672 KB Output isn't correct
7 Incorrect 41 ms 9672 KB Output isn't correct
8 Incorrect 39 ms 9800 KB Output isn't correct
9 Incorrect 71 ms 10172 KB Output isn't correct
10 Incorrect 103 ms 10256 KB Output isn't correct
11 Incorrect 226 ms 10440 KB Output isn't correct
12 Incorrect 235 ms 10840 KB Output isn't correct
13 Incorrect 461 ms 10876 KB Output isn't correct
14 Incorrect 911 ms 11128 KB Output isn't correct
15 Incorrect 939 ms 13504 KB Output isn't correct

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8096 ms 13936 KB Time limit exceeded
2 Execution timed out 8074 ms 13636 KB Time limit exceeded
3 Execution timed out 8016 ms 15544 KB Time limit exceeded
4 Incorrect 406 ms 11300 KB Output isn't correct
5 Incorrect 454 ms 12616 KB Output isn't correct
6 Execution timed out 8019 ms 12428 KB Time limit exceeded
7 Incorrect 6430 ms 13476 KB Output isn't correct
8 Incorrect 3711 ms 17848 KB Output isn't correct
9 Incorrect 5644 ms 18240 KB Output isn't correct
10 Execution timed out 8061 ms 22596 KB Time limit exceeded
11 Execution timed out 8029 ms 20248 KB Time limit exceeded
12 Execution timed out 8007 ms 19264 KB Time limit exceeded
13 Execution timed out 8047 ms 19884 KB Time limit exceeded
14 Execution timed out 8048 ms 20032 KB Time limit exceeded
15 Execution timed out 8029 ms 22988 KB Time limit exceeded
16 Execution timed out 8073 ms 28520 KB Time limit exceeded
17 Execution timed out 8035 ms 27352 KB Time limit exceeded