oj.uz

Submission #310329

# Submission time Handle Problem Language Result Execution time Memory
310329 2020-10-06T16:37:45 Z shivensinha4 Regions (IOI09_regions) C++17
60 / 100
 8000 ms 41900 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;
		}
		//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 4 ms 5632 KB Output is correct
2 Correct 4 ms 5632 KB Output is correct
3 Correct 5 ms 5632 KB Output is correct
4 Correct 8 ms 5632 KB Output is correct
5 Correct 12 ms 5760 KB Output is correct
6 Correct 21 ms 5888 KB Output is correct
7 Correct 26 ms 5928 KB Output is correct
8 Correct 56 ms 6008 KB Output is correct
9 Correct 76 ms 6904 KB Output is correct
10 Correct 140 ms 7160 KB Output is correct
11 Correct 228 ms 7928 KB Output is correct
12 Correct 208 ms 8888 KB Output is correct
13 Correct 356 ms 8696 KB Output is correct
14 Correct 628 ms 9824 KB Output is correct
15 Correct 762 ms 14412 KB Output is correct

Subtask #2
45.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 3639 ms 16204 KB Output is correct
2 Correct 4285 ms 14868 KB Output is correct
3 Correct 7852 ms 22192 KB Output is correct
4 Correct 538 ms 10376 KB Output is correct
5 Correct 704 ms 13820 KB Output is correct
6 Correct 1060 ms 13408 KB Output is correct
7 Correct 1144 ms 14524 KB Output is correct
8 Correct 3992 ms 25976 KB Output is correct
9 Correct 7945 ms 32720 KB Output is correct
10 Execution timed out 8074 ms 35088 KB Time limit exceeded
11 Execution timed out 8019 ms 29880 KB Time limit exceeded
12 Execution timed out 8054 ms 26328 KB Time limit exceeded
13 Execution timed out 8010 ms 27056 KB Time limit exceeded
14 Execution timed out 8004 ms 27144 KB Time limit exceeded
15 Execution timed out 8090 ms 33196 KB Time limit exceeded
16 Execution timed out 8093 ms 41900 KB Time limit exceeded
17 Execution timed out 8089 ms 40724 KB Time limit exceeded