oj.uz

Submission #310349

# Submission time Handle Problem Language Result Execution time Memory
310349 2020-10-06T17:00:47 Z shivensinha4 Regions (IOI09_regions) C++14
50 / 100
 8000 ms 41524 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 5 ms 5632 KB Output is correct
3 Correct 7 ms 5632 KB Output is correct
4 Correct 9 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 35 ms 6008 KB Output is correct
8 Correct 74 ms 6008 KB Output is correct
9 Correct 84 ms 6904 KB Output is correct
10 Correct 144 ms 7228 KB Output is correct
11 Correct 257 ms 7800 KB Output is correct
12 Correct 349 ms 8828 KB Output is correct
13 Correct 351 ms 8684 KB Output is correct
14 Correct 723 ms 9776 KB Output is correct
15 Correct 912 ms 14552 KB Output is correct

Subtask #2
35.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 4363 ms 15964 KB Output is correct
2 Correct 5179 ms 14848 KB Output is correct
3 Execution timed out 8077 ms 21156 KB Time limit exceeded
4 Correct 646 ms 10364 KB Output is correct
5 Correct 787 ms 13696 KB Output is correct
6 Correct 1086 ms 13344 KB Output is correct
7 Correct 1099 ms 14328 KB Output is correct
8 Correct 4314 ms 25760 KB Output is correct
9 Execution timed out 8042 ms 30332 KB Time limit exceeded
10 Execution timed out 8041 ms 34752 KB Time limit exceeded
11 Execution timed out 8041 ms 29412 KB Time limit exceeded
12 Execution timed out 8093 ms 26216 KB Time limit exceeded
13 Execution timed out 8054 ms 27068 KB Time limit exceeded
14 Execution timed out 8070 ms 27052 KB Time limit exceeded
15 Execution timed out 8095 ms 32860 KB Time limit exceeded
16 Execution timed out 8042 ms 41524 KB Time limit exceeded
17 Execution timed out 8082 ms 40752 KB Time limit exceeded