oj.uz

Submission #310336

# Submission time Handle Problem Language Result Execution time Memory
310336 2020-10-06T16:49:26 Z shivensinha4 Regions (IOI09_regions) C++17
50 / 100
 8000 ms 41268 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> 
    size_t operator()(const pair<T1, T2>& p) const
    { 
        auto hash1 = hash<T1>{}(p.first); 
        auto hash2 = hash<T2>{}(p.second); 
        return hash1 ^ hash2; 
    } 
}; 

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.find({r1, r2}) != seen.end()) {
			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 4 ms 5632 KB Output is correct
2 Correct 4 ms 5632 KB Output is correct
3 Correct 6 ms 5632 KB Output is correct
4 Correct 10 ms 5632 KB Output is correct
5 Correct 14 ms 5760 KB Output is correct
6 Correct 23 ms 5888 KB Output is correct
7 Correct 38 ms 6008 KB Output is correct
8 Correct 45 ms 6004 KB Output is correct
9 Correct 67 ms 6904 KB Output is correct
10 Correct 126 ms 7144 KB Output is correct
11 Correct 227 ms 7964 KB Output is correct
12 Correct 251 ms 8828 KB Output is correct
13 Correct 420 ms 8816 KB Output is correct
14 Correct 632 ms 9868 KB Output is correct
15 Correct 781 ms 14328 KB Output is correct

Subtask #2
35.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 3629 ms 16204 KB Output is correct
2 Correct 4310 ms 15044 KB Output is correct
3 Execution timed out 8047 ms 22216 KB Time limit exceeded
4 Correct 651 ms 10488 KB Output is correct
5 Correct 719 ms 13772 KB Output is correct
6 Correct 959 ms 13644 KB Output is correct
7 Correct 1126 ms 14372 KB Output is correct
8 Correct 4404 ms 25864 KB Output is correct
9 Execution timed out 8048 ms 32644 KB Time limit exceeded
10 Execution timed out 8051 ms 35448 KB Time limit exceeded
11 Execution timed out 8084 ms 29732 KB Time limit exceeded
12 Execution timed out 8019 ms 26092 KB Time limit exceeded
13 Execution timed out 8070 ms 26924 KB Time limit exceeded
14 Execution timed out 8048 ms 27004 KB Time limit exceeded
15 Execution timed out 8087 ms 32712 KB Time limit exceeded
16 Execution timed out 8068 ms 41268 KB Time limit exceeded
17 Execution timed out 8100 ms 40728 KB Time limit exceeded