oj.uz

Submission #493138

# Submission time Handle Problem Language Result Execution time Memory
493138 2021-12-10T06:33:08 Z flappybird Regions (IOI09_regions) C++17
40 / 100
 1076 ms 131076 KB 
#include <bits/stdc++.h>
#include <unordered_map>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")
using namespace std;
typedef int ll;
typedef pair<ll, ll> pll;
#define MAX 200010
#define MAXS 20
#define INF 1000000000000000001
#define bb ' '
#define ln '\n'
#define Ln '\n'
#define B 70
vector<ll> adj[MAX];
vector<ll> rr[MAX];
pll range[MAX];
ll rrr[MAX];
ll cnt = 0;
ll num[MAX];
vector<vector<ll>> tdp, bdp;
void dfs(ll x, ll p = 0) {
	range[x].first = range[x].second = ++cnt;
	tdp[x] = tdp[p];
	if (num[rrr[x]] != -1) tdp[x][num[rrr[x]]]++, bdp[x][num[rrr[x]]]++;
	for (auto v : adj[x]) {
		if (v == p) continue;
		dfs(v, x);
		range[x].second = max(range[x].second, range[v].second);
		for (ll i = 0; i < bdp[x].size(); i++) bdp[x][i] += bdp[v][i];
	}
}
signed main() {
	ios::sync_with_stdio(false), cin.tie(0);
	ll N, R, Q;
	cin >> N >> R >> Q;
	ll i;
	ll p, r;
	cin >> r;
	rr[r].push_back(1);
	rrr[1] = r;
	for (i = 2; i <= N; i++) {
		cin >> p >> r;
		rrr[i] = r;
		adj[p].push_back(i);
		adj[i].push_back(p);
		rr[r].push_back(i);
	}
	ll nn = 0;
	for (i = 0; i <= R; i++) {
		if (rr[i].size() >= B) num[i] = nn++;
		else num[i] = -1;
	}
	tdp = vector<vector<ll>>(N + 2, vector<ll>(nn));
	bdp = vector<vector<ll>>(N + 2, vector<ll>(nn));
	ll a, b;
	unordered_map<ll, bool> chk;
	unordered_map<ll, long long> val;
	dfs(1);
	for (i = 1; i <= Q; i++) {
		cin >> a >> b;
		if (chk[a * 25001 + b]) cout << val[a * 25001 + b] << endl;
		else {
			long long ans = 0;
			if (rr[a].size() < rr[b].size()) {
				if (num[b] != -1) {
					for (auto x : rr[a]) ans += bdp[x][num[b]];
				}
				else {
					for (auto x : rr[a]) {
						for (auto y : rr[b]) {
							if (range[x].first <= range[y].first && range[y].second <= range[x].second) ans++;
						}
					}
				}
			}
			else {
				if (num[a] != -1) {
					for (auto x : rr[b]) ans += tdp[x][num[a]];
				}
				else {
					for (auto x : rr[a]) {
						for (auto y : rr[b]) {
							if (range[x].first <= range[y].first && range[y].second <= range[x].second) ans++;
						}
					}
				}
			}
			chk[a * 25001 + b] = 1;
			val[a * 25001 + b] = ans;
			cout << ans << endl;
		}
	}
}

Compilation message

regions.cpp: In function 'void dfs(ll, ll)':
regions.cpp:32:20: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |   for (ll i = 0; i < bdp[x].size(); i++) bdp[x][i] += bdp[v][i];
      |                  ~~^~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9672 KB Output is correct
2 Correct 6 ms 9672 KB Output is correct
3 Correct 8 ms 9708 KB Output is correct
4 Correct 9 ms 9768 KB Output is correct
5 Correct 13 ms 9816 KB Output is correct
6 Correct 20 ms 10056 KB Output is correct
7 Correct 19 ms 10044 KB Output is correct
8 Correct 43 ms 10088 KB Output is correct
9 Correct 66 ms 11080 KB Output is correct
10 Correct 111 ms 11472 KB Output is correct
11 Correct 188 ms 13312 KB Output is correct
12 Correct 210 ms 14468 KB Output is correct
13 Correct 238 ms 49984 KB Output is correct
14 Correct 203 ms 61736 KB Output is correct
15 Correct 281 ms 95020 KB Output is correct

Subtask #2
25.0 / 85.0

# Verdict Execution time Memory Grader output
1 Runtime error 82 ms 131076 KB Execution killed with signal 9
2 Correct 1076 ms 125192 KB Output is correct
3 Runtime error 80 ms 131076 KB Execution killed with signal 9
4 Correct 158 ms 39588 KB Output is correct
5 Correct 405 ms 48632 KB Output is correct
6 Correct 481 ms 44196 KB Output is correct
7 Correct 751 ms 82180 KB Output is correct
8 Runtime error 90 ms 131076 KB Execution killed with signal 9
9 Runtime error 98 ms 131076 KB Execution killed with signal 9
10 Runtime error 97 ms 131076 KB Execution killed with signal 9
11 Runtime error 108 ms 131076 KB Execution killed with signal 9
12 Runtime error 109 ms 131076 KB Execution killed with signal 9
13 Runtime error 103 ms 131076 KB Execution killed with signal 9
14 Runtime error 120 ms 131076 KB Execution killed with signal 9
15 Runtime error 104 ms 131076 KB Execution killed with signal 9
16 Runtime error 103 ms 131076 KB Execution killed with signal 9
17 Runtime error 115 ms 131076 KB Execution killed with signal 9