oj.uz

Submission #310320

# Submission time Handle Problem Language Result Execution time Memory
310320 2020-10-06T16:26:02 Z shivensinha4 Regions (IOI09_regions) C++17
40 / 100
 8000 ms 40688 KB 
#include <bits/stdc++.h> 
using namespace std; 
#define for_(i, s, e) for (int i = s; i < (int) e; i++)
#define for__(i, s, e) for (ll i = s; i < e; i++)
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
//#define endl '\n'

const int MXN = 200000, MXR = 25000, INF = 1e9+1;
int n, r, q;
int reg[MXN+1], tin[MXN+1], tout[MXN+1], pt = 0;
vi adj[MXN+1];
vector<vi> regList[MXR+1];

void dfs(int p, int parent) {
	regList[reg[p]].push_back({pt, p});
	tin[p] = pt++;
	for (int i: adj[p]) if (i != parent) dfs(i, p);
	tout[p] = pt-1;
}

int main() {
	#ifdef shiven
	freopen("test.in", "r", stdin);
	#endif
	
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	cin >> n >> r >> q;
	cin >> reg[0];
	reg[0] -= 1;
	for_(i, 1, n) {
		int p; cin >> p >> reg[i];
		reg[i] -= 1;
		adj[p-1].push_back(i);
	}
	
	dfs(0, 0);
	
	while (q--) {
		int r1, r2; cin >> r1 >> r2;
		r1 -= 1; r2 -= 1;
		//cout << r1 << " " << r2 << endl;
		int ans = 0;
		for (auto i: regList[r1]) {
			auto pta = lower_bound(regList[r2].begin(), regList[r2].end(), (vi) {tin[i[1]]+1, -1});
			auto ptb = upper_bound(regList[r2].begin(), regList[r2].end(), (vi) {tout[i[1]], INF});
			//cout << ptb-pta << endl;
			ans += ptb-pta;
		}
		cout << ans << endl;
	}

	return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5632 KB Output is correct
2 Correct 4 ms 5632 KB Output is correct
3 Correct 6 ms 5632 KB Output is correct
4 Correct 9 ms 5632 KB Output is correct
5 Correct 13 ms 5632 KB Output is correct
6 Correct 23 ms 5760 KB Output is correct
7 Correct 36 ms 5760 KB Output is correct
8 Correct 50 ms 5888 KB Output is correct
9 Correct 81 ms 6528 KB Output is correct
10 Correct 98 ms 6776 KB Output is correct
11 Correct 205 ms 7296 KB Output is correct
12 Correct 267 ms 8312 KB Output is correct
13 Correct 385 ms 8184 KB Output is correct
14 Correct 738 ms 9080 KB Output is correct
15 Correct 846 ms 13304 KB Output is correct

Subtask #2
25.0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8087 ms 14328 KB Time limit exceeded
2 Execution timed out 8073 ms 13172 KB Time limit exceeded
3 Execution timed out 8067 ms 17520 KB Time limit exceeded
4 Correct 669 ms 8960 KB Output is correct
5 Correct 693 ms 11512 KB Output is correct
6 Correct 3744 ms 11128 KB Output is correct
7 Correct 5222 ms 13176 KB Output is correct
8 Correct 5352 ms 21240 KB Output is correct
9 Execution timed out 8039 ms 23544 KB Time limit exceeded
10 Execution timed out 8061 ms 30200 KB Time limit exceeded
11 Execution timed out 8058 ms 24540 KB Time limit exceeded
12 Execution timed out 8084 ms 25584 KB Time limit exceeded
13 Execution timed out 8060 ms 26224 KB Time limit exceeded
14 Execution timed out 8016 ms 26176 KB Time limit exceeded
15 Execution timed out 8031 ms 32004 KB Time limit exceeded
16 Execution timed out 8073 ms 40688 KB Time limit exceeded
17 Execution timed out 8013 ms 39560 KB Time limit exceeded