oj.uz

Submission #310332

# Submission time Handle Problem Language Result Execution time Memory
310332 2020-10-06T16:44:57 Z shivensinha4 Regions (IOI09_regions) C++17
60 / 100
 8000 ms 43376 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*10);
	
	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;
		}
		//cout << r1 << " " << r2 << endl;
		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});
			//cout << ptb-pta << endl;
			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 7680 KB Output is correct
2 Correct 6 ms 7680 KB Output is correct
3 Correct 8 ms 7680 KB Output is correct
4 Correct 11 ms 7680 KB Output is correct
5 Correct 10 ms 7780 KB Output is correct
6 Correct 29 ms 7928 KB Output is correct
7 Correct 49 ms 7928 KB Output is correct
8 Correct 46 ms 8184 KB Output is correct
9 Correct 75 ms 8824 KB Output is correct
10 Correct 153 ms 9080 KB Output is correct
11 Correct 244 ms 9720 KB Output is correct
12 Correct 248 ms 10744 KB Output is correct
13 Correct 338 ms 10788 KB Output is correct
14 Correct 591 ms 11648 KB Output is correct
15 Correct 788 ms 16104 KB Output is correct

Subtask #2
45.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 3560 ms 18144 KB Output is correct
2 Correct 4204 ms 16828 KB Output is correct
3 Correct 7752 ms 22752 KB Output is correct
4 Correct 512 ms 12260 KB Output is correct
5 Correct 560 ms 15108 KB Output is correct
6 Correct 859 ms 14680 KB Output is correct
7 Correct 1091 ms 16344 KB Output is correct
8 Correct 3757 ms 26532 KB Output is correct
9 Correct 7913 ms 31916 KB Output is correct
10 Execution timed out 8090 ms 36168 KB Time limit exceeded
11 Execution timed out 8071 ms 30284 KB Time limit exceeded
12 Execution timed out 8012 ms 28236 KB Time limit exceeded
13 Execution timed out 8019 ms 29004 KB Time limit exceeded
14 Execution timed out 8080 ms 29012 KB Time limit exceeded
15 Execution timed out 8096 ms 34732 KB Time limit exceeded
16 Execution timed out 8089 ms 43376 KB Time limit exceeded
17 Execution timed out 8004 ms 42580 KB Time limit exceeded