oj.uz

Submission #310340

# Submission time Handle Problem Language Result Execution time Memory
310340 2020-10-06T16:51:59 Z shivensinha4 Regions (IOI09_regions) C++17
50 / 100
 8000 ms 41616 KB 
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#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 5 ms 5632 KB Output is correct
2 Correct 5 ms 5632 KB Output is correct
3 Correct 7 ms 5632 KB Output is correct
4 Correct 7 ms 5704 KB Output is correct
5 Correct 18 ms 5664 KB Output is correct
6 Correct 25 ms 5888 KB Output is correct
7 Correct 43 ms 5888 KB Output is correct
8 Correct 60 ms 6008 KB Output is correct
9 Correct 59 ms 6892 KB Output is correct
10 Correct 190 ms 7264 KB Output is correct
11 Correct 238 ms 7800 KB Output is correct
12 Correct 315 ms 8824 KB Output is correct
13 Correct 456 ms 8856 KB Output is correct
14 Correct 803 ms 9916 KB Output is correct
15 Correct 1034 ms 14200 KB Output is correct

Subtask #2
35.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 4454 ms 15976 KB Output is correct
2 Correct 5749 ms 14800 KB Output is correct
3 Execution timed out 8045 ms 20868 KB Time limit exceeded
4 Correct 709 ms 10516 KB Output is correct
5 Correct 844 ms 13700 KB Output is correct
6 Correct 1162 ms 13368 KB Output is correct
7 Correct 1319 ms 14284 KB Output is correct
8 Correct 4238 ms 25656 KB Output is correct
9 Execution timed out 8022 ms 30360 KB Time limit exceeded
10 Execution timed out 8047 ms 34904 KB Time limit exceeded
11 Execution timed out 8044 ms 29544 KB Time limit exceeded
12 Execution timed out 8064 ms 26276 KB Time limit exceeded
13 Execution timed out 8009 ms 26924 KB Time limit exceeded
14 Execution timed out 8077 ms 27104 KB Time limit exceeded
15 Execution timed out 8085 ms 32876 KB Time limit exceeded
16 Execution timed out 8039 ms 41616 KB Time limit exceeded
17 Execution timed out 8054 ms 40524 KB Time limit exceeded