oj.uz

Submission #310348

# Submission time Handle Problem Language Result Execution time Memory
310348 2020-10-06T17:00:33 Z shivensinha4 Regions (IOI09_regions) C++17
50 / 100
 8000 ms 41684 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<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.count({r1, 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 4 ms 5632 KB Output is correct
2 Correct 4 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 13 ms 5760 KB Output is correct
6 Correct 16 ms 5912 KB Output is correct
7 Correct 39 ms 5888 KB Output is correct
8 Correct 44 ms 6008 KB Output is correct
9 Correct 71 ms 6908 KB Output is correct
10 Correct 133 ms 7420 KB Output is correct
11 Correct 246 ms 7928 KB Output is correct
12 Correct 254 ms 8952 KB Output is correct
13 Correct 324 ms 8864 KB Output is correct
14 Correct 617 ms 9888 KB Output is correct
15 Correct 832 ms 14328 KB Output is correct

Subtask #2
35.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 4125 ms 16100 KB Output is correct
2 Correct 4854 ms 14912 KB Output is correct
3 Execution timed out 8006 ms 21000 KB Time limit exceeded
4 Correct 693 ms 10324 KB Output is correct
5 Correct 654 ms 13660 KB Output is correct
6 Correct 927 ms 13440 KB Output is correct
7 Correct 1400 ms 14344 KB Output is correct
8 Correct 4749 ms 25752 KB Output is correct
9 Execution timed out 8036 ms 32472 KB Time limit exceeded
10 Execution timed out 8080 ms 34708 KB Time limit exceeded
11 Execution timed out 8058 ms 29424 KB Time limit exceeded
12 Execution timed out 8100 ms 26288 KB Time limit exceeded
13 Execution timed out 8093 ms 26928 KB Time limit exceeded
14 Execution timed out 8085 ms 27036 KB Time limit exceeded
15 Execution timed out 8021 ms 33020 KB Time limit exceeded
16 Execution timed out 8085 ms 41684 KB Time limit exceeded
17 Execution timed out 8038 ms 40676 KB Time limit exceeded