oj.uz

Submission #310337

# Submission time Handle Problem Language Result Execution time Memory
310337 2020-10-06T16:50:31 Z shivensinha4 Regions (IOI09_regions) C++17
50 / 100
 8000 ms 50512 KB 
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
#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<ii, int, pair_hash> 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.find({r1, r2}) != seen.end()) {
			cout << seen[{r1, r2}] << endl;
			continue;
		}
		
		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});
			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 4 ms 5632 KB Output is correct
2 Correct 5 ms 5632 KB Output is correct
3 Correct 7 ms 5632 KB Output is correct
4 Correct 10 ms 5632 KB Output is correct
5 Correct 11 ms 5760 KB Output is correct
6 Correct 30 ms 5888 KB Output is correct
7 Correct 39 ms 6008 KB Output is correct
8 Correct 46 ms 6008 KB Output is correct
9 Correct 66 ms 7168 KB Output is correct
10 Correct 134 ms 7164 KB Output is correct
11 Correct 264 ms 7800 KB Output is correct
12 Correct 256 ms 9080 KB Output is correct
13 Correct 407 ms 8824 KB Output is correct
14 Correct 635 ms 9592 KB Output is correct
15 Correct 828 ms 16376 KB Output is correct

Subtask #2
35.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 4487 ms 16824 KB Output is correct
2 Correct 5161 ms 14896 KB Output is correct
3 Execution timed out 8037 ms 22480 KB Time limit exceeded
4 Correct 685 ms 10488 KB Output is correct
5 Correct 819 ms 14980 KB Output is correct
6 Correct 981 ms 13560 KB Output is correct
7 Correct 1191 ms 14536 KB Output is correct
8 Correct 5348 ms 28944 KB Output is correct
9 Execution timed out 8013 ms 30484 KB Time limit exceeded
10 Execution timed out 8060 ms 38884 KB Time limit exceeded
11 Execution timed out 8067 ms 29668 KB Time limit exceeded
12 Execution timed out 8054 ms 26024 KB Time limit exceeded
13 Execution timed out 8038 ms 27700 KB Time limit exceeded
14 Execution timed out 8087 ms 27040 KB Time limit exceeded
15 Execution timed out 8099 ms 35884 KB Time limit exceeded
16 Execution timed out 8076 ms 50512 KB Time limit exceeded
17 Execution timed out 8026 ms 48156 KB Time limit exceeded