oj.uz

Submission #310345

# Submission time Handle Problem Language Result Execution time Memory
310345 2020-10-06T16:56:32 Z shivensinha4 Regions (IOI09_regions) C++17
55 / 100
 8000 ms 42756 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];
map<int, int> seen[MXR+1];

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[r1].count(r2)) {
			cout << seen[r1][r2] << endl;
			continue;
		}
		
		int ans = 0;
		for (auto i: regList[r1]) {
			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 6 ms 6784 KB Output is correct
2 Correct 5 ms 6784 KB Output is correct
3 Correct 7 ms 6784 KB Output is correct
4 Correct 12 ms 6784 KB Output is correct
5 Correct 13 ms 6912 KB Output is correct
6 Correct 22 ms 7040 KB Output is correct
7 Correct 37 ms 7124 KB Output is correct
8 Correct 52 ms 7248 KB Output is correct
9 Correct 67 ms 7932 KB Output is correct
10 Correct 90 ms 8280 KB Output is correct
11 Correct 234 ms 8824 KB Output is correct
12 Correct 262 ms 9848 KB Output is correct
13 Correct 357 ms 9720 KB Output is correct
14 Correct 613 ms 10744 KB Output is correct
15 Correct 766 ms 15236 KB Output is correct

Subtask #2
40.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 3797 ms 16904 KB Output is correct
2 Correct 4556 ms 15844 KB Output is correct
3 Correct 7099 ms 22096 KB Output is correct
4 Correct 610 ms 11384 KB Output is correct
5 Correct 651 ms 14328 KB Output is correct
6 Correct 1006 ms 13760 KB Output is correct
7 Correct 1398 ms 15368 KB Output is correct
8 Correct 4347 ms 25624 KB Output is correct
9 Execution timed out 8028 ms 30888 KB Time limit exceeded
10 Execution timed out 8016 ms 34708 KB Time limit exceeded
11 Execution timed out 8032 ms 29672 KB Time limit exceeded
12 Execution timed out 8061 ms 27392 KB Time limit exceeded
13 Execution timed out 8039 ms 28220 KB Time limit exceeded
14 Execution timed out 8087 ms 28196 KB Time limit exceeded
15 Execution timed out 8067 ms 34104 KB Time limit exceeded
16 Execution timed out 8071 ms 42756 KB Time limit exceeded
17 Execution timed out 8050 ms 41936 KB Time limit exceeded