oj.uz

Submission #310334

# Submission time Handle Problem Language Result Execution time Memory
310334 2020-10-06T16:46:25 Z shivensinha4 Regions (IOI09_regions) C++17
50 / 100
 8000 ms 131076 KB 
#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;
	seen.reserve(r*1000);
	
	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 5 ms 5632 KB Output is correct
2 Correct 4 ms 5632 KB Output is correct
3 Correct 8 ms 5760 KB Output is correct
4 Correct 8 ms 6016 KB Output is correct
5 Correct 19 ms 6144 KB Output is correct
6 Correct 40 ms 7928 KB Output is correct
7 Correct 53 ms 7160 KB Output is correct
8 Correct 41 ms 7708 KB Output is correct
9 Correct 68 ms 9336 KB Output is correct
10 Correct 158 ms 10488 KB Output is correct
11 Correct 278 ms 9848 KB Output is correct
12 Correct 282 ms 12536 KB Output is correct
13 Correct 435 ms 11384 KB Output is correct
14 Correct 668 ms 11248 KB Output is correct
15 Correct 802 ms 16148 KB Output is correct

Subtask #2
35.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 4290 ms 17360 KB Output is correct
2 Correct 5050 ms 16328 KB Output is correct
3 Execution timed out 8051 ms 22684 KB Time limit exceeded
4 Correct 590 ms 41648 KB Output is correct
5 Correct 692 ms 53240 KB Output is correct
6 Correct 1016 ms 71912 KB Output is correct
7 Correct 1253 ms 95108 KB Output is correct
8 Correct 3938 ms 105852 KB Output is correct
9 Runtime error 116 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
10 Runtime error 80 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
11 Runtime error 78 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
12 Runtime error 77 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
13 Runtime error 81 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
14 Runtime error 79 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
15 Runtime error 78 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
16 Runtime error 78 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
17 Runtime error 78 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)