oj.uz

Submission #310333

# Submission time Handle Problem Language Result Execution time Memory
310333 2020-10-06T16:45:54 Z shivensinha4 Regions (IOI09_regions) C++17
0 / 100
 82 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(MXR*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
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 82 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Runtime error 68 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 Runtime error 78 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
4 Runtime error 74 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
5 Runtime error 71 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
6 Runtime error 75 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
7 Runtime error 75 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
8 Runtime error 76 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
9 Runtime error 79 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
10 Runtime error 75 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
11 Runtime error 75 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
12 Runtime error 75 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
13 Runtime error 69 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
14 Runtime error 73 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
15 Runtime error 67 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Runtime error 73 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Runtime error 82 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 Runtime error 77 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
4 Runtime error 76 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
5 Runtime error 78 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
6 Runtime error 70 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
7 Runtime error 73 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
8 Runtime error 74 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
9 Runtime error 75 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
10 Runtime error 74 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
11 Runtime error 74 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
12 Runtime error 74 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
13 Runtime error 74 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
14 Runtime error 72 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
15 Runtime error 74 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
16 Runtime error 74 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
17 Runtime error 76 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)