oj.uz

Submission #310346

# Submission time Handle Problem Language Result Execution time Memory
310346 2020-10-06T16:56:43 Z shivensinha4 Regions (IOI09_regions) C++17
55 / 100
 8000 ms 43040 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'

//struct pair_hash
//{
	//template <class T1, class T2>
	//std::size_t operator() (const std::pair<T1, T2> &pair) const
	//{
		//return std::hash<T1>()(pair.first) ^ std::hash<T2>()(pair.second);
	//}
//};

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];
unordered_map<int, int> seen[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;
		if (seen[r1].count(r2)) {
			cout << seen[r1][r2] << endl;
			continue;
		}
		
		int ans = 0;
		for (auto i: regList[r1]) {
			ans += upper_bound(regList[r2].begin(), regList[r2].end(), (vi) {tout[i[1]], INF})-lower_bound(regList[r2].begin(), regList[r2].end(), (vi) {tin[i[1]]+1, -1});
		}
		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 7040 KB Output is correct
2 Correct 6 ms 7040 KB Output is correct
3 Correct 8 ms 7040 KB Output is correct
4 Correct 11 ms 7040 KB Output is correct
5 Correct 10 ms 7132 KB Output is correct
6 Correct 26 ms 7288 KB Output is correct
7 Correct 37 ms 7292 KB Output is correct
8 Correct 60 ms 7552 KB Output is correct
9 Correct 69 ms 8160 KB Output is correct
10 Correct 124 ms 8440 KB Output is correct
11 Correct 305 ms 9156 KB Output is correct
12 Correct 304 ms 10080 KB Output is correct
13 Correct 363 ms 9976 KB Output is correct
14 Correct 644 ms 11040 KB Output is correct
15 Correct 872 ms 15492 KB Output is correct

Subtask #2
40.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 3672 ms 16928 KB Output is correct
2 Correct 4340 ms 15796 KB Output is correct
3 Correct 6436 ms 21924 KB Output is correct
4 Correct 546 ms 11548 KB Output is correct
5 Correct 755 ms 14408 KB Output is correct
6 Correct 1125 ms 13972 KB Output is correct
7 Correct 1079 ms 15524 KB Output is correct
8 Correct 4483 ms 25560 KB Output is correct
9 Execution timed out 8052 ms 30080 KB Time limit exceeded
10 Execution timed out 8042 ms 34860 KB Time limit exceeded
11 Execution timed out 8058 ms 29624 KB Time limit exceeded
12 Execution timed out 8026 ms 27432 KB Time limit exceeded
13 Execution timed out 8055 ms 28540 KB Time limit exceeded
14 Execution timed out 8082 ms 28348 KB Time limit exceeded
15 Execution timed out 8076 ms 34280 KB Time limit exceeded
16 Execution timed out 8023 ms 43040 KB Time limit exceeded
17 Execution timed out 8023 ms 42256 KB Time limit exceeded