oj.uz

Submission #310342

# Submission time Handle Problem Language Result Execution time Memory
310342 2020-10-06T16:53:58 Z shivensinha4 Regions (IOI09_regions) C++17
55 / 100
 8000 ms 42856 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<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]) {
			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
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7040 KB Output is correct
2 Correct 5 ms 7040 KB Output is correct
3 Correct 7 ms 7040 KB Output is correct
4 Correct 11 ms 7040 KB Output is correct
5 Correct 14 ms 7040 KB Output is correct
6 Correct 35 ms 7232 KB Output is correct
7 Correct 48 ms 7444 KB Output is correct
8 Correct 52 ms 7424 KB Output is correct
9 Correct 78 ms 8228 KB Output is correct
10 Correct 152 ms 8440 KB Output is correct
11 Correct 279 ms 9060 KB Output is correct
12 Correct 313 ms 10100 KB Output is correct
13 Correct 378 ms 9964 KB Output is correct
14 Correct 811 ms 10872 KB Output is correct
15 Correct 891 ms 15232 KB Output is correct

Subtask #2
40.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 3830 ms 17344 KB Output is correct
2 Correct 4319 ms 15872 KB Output is correct
3 Correct 7122 ms 22076 KB Output is correct
4 Correct 540 ms 11704 KB Output is correct
5 Correct 749 ms 14520 KB Output is correct
6 Correct 1036 ms 13996 KB Output is correct
7 Correct 1177 ms 15904 KB Output is correct
8 Correct 4543 ms 25464 KB Output is correct
9 Execution timed out 8055 ms 30428 KB Time limit exceeded
10 Execution timed out 8012 ms 34868 KB Time limit exceeded
11 Execution timed out 8012 ms 29532 KB Time limit exceeded
12 Execution timed out 8042 ms 27296 KB Time limit exceeded
13 Execution timed out 8054 ms 28508 KB Time limit exceeded
14 Execution timed out 8010 ms 28028 KB Time limit exceeded
15 Execution timed out 8021 ms 34296 KB Time limit exceeded
16 Execution timed out 8058 ms 42856 KB Time limit exceeded
17 Execution timed out 8022 ms 42080 KB Time limit exceeded