oj.uz

Submission #310331

# Submission time Handle Problem Language Result Execution time Memory
310331 2020-10-06T16:42:31 Z shivensinha4 Regions (IOI09_regions) C++17
45 / 100
 8000 ms 41856 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>
	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];
gp_hash_table<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;
		}
		//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 5 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 9 ms 5632 KB Output is correct
5 Correct 13 ms 5760 KB Output is correct
6 Correct 29 ms 5888 KB Output is correct
7 Correct 57 ms 6136 KB Output is correct
8 Correct 58 ms 6140 KB Output is correct
9 Correct 112 ms 7160 KB Output is correct
10 Correct 208 ms 7288 KB Output is correct
11 Correct 408 ms 8348 KB Output is correct
12 Correct 499 ms 9076 KB Output is correct
13 Correct 711 ms 9084 KB Output is correct
14 Correct 980 ms 9972 KB Output is correct
15 Correct 1351 ms 14276 KB Output is correct

Subtask #2
30.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 6103 ms 16228 KB Output is correct
2 Correct 6492 ms 15052 KB Output is correct
3 Execution timed out 8026 ms 20996 KB Time limit exceeded
4 Correct 1618 ms 10792 KB Output is correct
5 Correct 2849 ms 14808 KB Output is correct
6 Correct 2987 ms 14472 KB Output is correct
7 Correct 1604 ms 15024 KB Output is correct
8 Execution timed out 8076 ms 24448 KB Time limit exceeded
9 Execution timed out 8060 ms 27000 KB Time limit exceeded
10 Execution timed out 8010 ms 33664 KB Time limit exceeded
11 Execution timed out 8063 ms 27836 KB Time limit exceeded
12 Execution timed out 8047 ms 26924 KB Time limit exceeded
13 Execution timed out 8063 ms 27456 KB Time limit exceeded
14 Execution timed out 8026 ms 27208 KB Time limit exceeded
15 Execution timed out 8025 ms 33088 KB Time limit exceeded
16 Execution timed out 8050 ms 41856 KB Time limit exceeded
17 Execution timed out 8071 ms 41452 KB Time limit exceeded