oj.uz

Submission #310324

# Submission time Handle Problem Language Result Execution time Memory
310324 2020-10-06T16:29:45 Z shivensinha4 Regions (IOI09_regions) C++17
55 / 100
 8000 ms 41508 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];
map<ii, int> seen;

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;
		if (seen.count({r1, r2})) {
			cout << seen[{r1, r2}] << endl;
			continue;
		}
		//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;
		seen[{r1, r2}] = ans;
	}

	return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5632 KB Output is correct
2 Correct 4 ms 5632 KB Output is correct
3 Correct 8 ms 5632 KB Output is correct
4 Correct 11 ms 5632 KB Output is correct
5 Correct 14 ms 5888 KB Output is correct
6 Correct 25 ms 5888 KB Output is correct
7 Correct 43 ms 6008 KB Output is correct
8 Correct 47 ms 6084 KB Output is correct
9 Correct 77 ms 6904 KB Output is correct
10 Correct 151 ms 7176 KB Output is correct
11 Correct 230 ms 7932 KB Output is correct
12 Correct 297 ms 8928 KB Output is correct
13 Correct 399 ms 8936 KB Output is correct
14 Correct 678 ms 9900 KB Output is correct
15 Correct 840 ms 14240 KB Output is correct

Subtask #2
40.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 3434 ms 16152 KB Output is correct
2 Correct 4073 ms 14900 KB Output is correct
3 Correct 7048 ms 21668 KB Output is correct
4 Correct 638 ms 10740 KB Output is correct
5 Correct 713 ms 13776 KB Output is correct
6 Correct 1095 ms 13240 KB Output is correct
7 Correct 1554 ms 14436 KB Output is correct
8 Correct 4424 ms 25480 KB Output is correct
9 Execution timed out 8064 ms 30864 KB Time limit exceeded
10 Execution timed out 8032 ms 34472 KB Time limit exceeded
11 Execution timed out 8016 ms 29848 KB Time limit exceeded
12 Execution timed out 8055 ms 26264 KB Time limit exceeded
13 Execution timed out 8080 ms 27104 KB Time limit exceeded
14 Execution timed out 8009 ms 27052 KB Time limit exceeded
15 Execution timed out 8026 ms 32884 KB Time limit exceeded
16 Execution timed out 8042 ms 41508 KB Time limit exceeded
17 Execution timed out 8077 ms 40584 KB Time limit exceeded