oj.uz

Submission #310338

# Submission time Handle Problem Language Result Execution time Memory
310338 2020-10-06T16:51:09 Z shivensinha4 Regions (IOI09_regions) C++17
50 / 100
 8000 ms 41444 KB 
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#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];
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;
}

Compilation message

regions.cpp:2: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    2 | #pragma GCC optimization ("O3")
      | 
regions.cpp:3: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    3 | #pragma GCC optimization ("unroll-loops")
      |

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 8 ms 5632 KB Output is correct
4 Correct 8 ms 5632 KB Output is correct
5 Correct 13 ms 5760 KB Output is correct
6 Correct 20 ms 5888 KB Output is correct
7 Correct 38 ms 6008 KB Output is correct
8 Correct 44 ms 6008 KB Output is correct
9 Correct 69 ms 6904 KB Output is correct
10 Correct 138 ms 7160 KB Output is correct
11 Correct 220 ms 7800 KB Output is correct
12 Correct 259 ms 8824 KB Output is correct
13 Correct 378 ms 8696 KB Output is correct
14 Correct 828 ms 9824 KB Output is correct
15 Correct 1121 ms 14244 KB Output is correct

Subtask #2
35.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 4900 ms 15960 KB Output is correct
2 Correct 5576 ms 14916 KB Output is correct
3 Execution timed out 8025 ms 20588 KB Time limit exceeded
4 Correct 712 ms 10360 KB Output is correct
5 Correct 652 ms 13648 KB Output is correct
6 Correct 862 ms 13468 KB Output is correct
7 Correct 1231 ms 14440 KB Output is correct
8 Correct 4860 ms 25864 KB Output is correct
9 Execution timed out 8084 ms 29836 KB Time limit exceeded
10 Execution timed out 8080 ms 33688 KB Time limit exceeded
11 Execution timed out 8041 ms 28976 KB Time limit exceeded
12 Execution timed out 8090 ms 26116 KB Time limit exceeded
13 Execution timed out 8013 ms 27024 KB Time limit exceeded
14 Execution timed out 8092 ms 26732 KB Time limit exceeded
15 Execution timed out 8077 ms 32632 KB Time limit exceeded
16 Execution timed out 8080 ms 41444 KB Time limit exceeded
17 Execution timed out 8026 ms 40700 KB Time limit exceeded