oj.uz

Submission #477611

# Submission time Handle Problem Language Result Execution time Memory
477611 2021-10-02T19:30:43 Z Abrar_Al_Samit Regions (IOI09_regions) C++17
40 / 100
 8000 ms 28592 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]) {
			int cur = 0;
			for(auto it2 : reg[r1]) {
				cur += anc(it2, it);
			}
			ans += cur;
		}
		cout << ans << endl;
	}
	return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9672 KB Output is correct
2 Correct 6 ms 9672 KB Output is correct
3 Correct 8 ms 9672 KB Output is correct
4 Correct 12 ms 9672 KB Output is correct
5 Correct 11 ms 9672 KB Output is correct
6 Correct 28 ms 9672 KB Output is correct
7 Correct 27 ms 9672 KB Output is correct
8 Correct 21 ms 9800 KB Output is correct
9 Correct 64 ms 10184 KB Output is correct
10 Correct 61 ms 10116 KB Output is correct
11 Correct 148 ms 10440 KB Output is correct
12 Correct 258 ms 10892 KB Output is correct
13 Correct 406 ms 10824 KB Output is correct
14 Correct 907 ms 11072 KB Output is correct
15 Correct 878 ms 13504 KB Output is correct

Subtask #2
25.0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8023 ms 13888 KB Time limit exceeded
2 Execution timed out 8016 ms 13636 KB Time limit exceeded
3 Execution timed out 8031 ms 15576 KB Time limit exceeded
4 Correct 410 ms 11252 KB Output is correct
5 Correct 488 ms 12608 KB Output is correct
6 Execution timed out 8060 ms 12508 KB Time limit exceeded
7 Correct 6641 ms 13348 KB Output is correct
8 Correct 3474 ms 17868 KB Output is correct
9 Correct 5676 ms 18284 KB Output is correct
10 Execution timed out 8064 ms 22624 KB Time limit exceeded
11 Execution timed out 8034 ms 20164 KB Time limit exceeded
12 Execution timed out 8077 ms 19136 KB Time limit exceeded
13 Execution timed out 8007 ms 19936 KB Time limit exceeded
14 Execution timed out 8032 ms 20032 KB Time limit exceeded
15 Execution timed out 8034 ms 23060 KB Time limit exceeded
16 Execution timed out 8042 ms 28592 KB Time limit exceeded
17 Execution timed out 8003 ms 27344 KB Time limit exceeded