oj.uz

Submission #310351

# Submission time Handle Problem Language Result Execution time Memory
310351 2020-10-06T17:02:30 Z shivensinha4 Regions (IOI09_regions) C++17
60 / 100
 8000 ms 43712 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;
	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]) {
			//cout << ptb-pta << endl;
			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 7 ms 7680 KB Output is correct
2 Correct 5 ms 7680 KB Output is correct
3 Correct 9 ms 7680 KB Output is correct
4 Correct 10 ms 7680 KB Output is correct
5 Correct 17 ms 7680 KB Output is correct
6 Correct 22 ms 7928 KB Output is correct
7 Correct 51 ms 7928 KB Output is correct
8 Correct 53 ms 8056 KB Output is correct
9 Correct 72 ms 8828 KB Output is correct
10 Correct 154 ms 9080 KB Output is correct
11 Correct 261 ms 9720 KB Output is correct
12 Correct 287 ms 10744 KB Output is correct
13 Correct 469 ms 10616 KB Output is correct
14 Correct 684 ms 11640 KB Output is correct
15 Correct 981 ms 15928 KB Output is correct

Subtask #2
45.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 4550 ms 17876 KB Output is correct
2 Correct 4865 ms 16632 KB Output is correct
3 Correct 7664 ms 22656 KB Output is correct
4 Correct 567 ms 12240 KB Output is correct
5 Correct 680 ms 15212 KB Output is correct
6 Correct 897 ms 14948 KB Output is correct
7 Correct 1146 ms 16120 KB Output is correct
8 Correct 3766 ms 26452 KB Output is correct
9 Correct 7915 ms 32196 KB Output is correct
10 Execution timed out 8071 ms 36260 KB Time limit exceeded
11 Execution timed out 8077 ms 30960 KB Time limit exceeded
12 Execution timed out 8032 ms 28456 KB Time limit exceeded
13 Execution timed out 8069 ms 29056 KB Time limit exceeded
14 Execution timed out 8013 ms 28920 KB Time limit exceeded
15 Execution timed out 8101 ms 35064 KB Time limit exceeded
16 Execution timed out 8023 ms 43712 KB Time limit exceeded
17 Execution timed out 8058 ms 42680 KB Time limit exceeded