oj.uz

Submission #493137

# Submission time Handle Problem Language Result Execution time Memory
493137 2021-12-10T06:32:39 Z flappybird Regions (IOI09_regions) C++17
29 / 100
 498 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 long long 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 'long long int'} and 'std::vector<long long 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
14.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9672 KB Output is correct
2 Correct 6 ms 9616 KB Output is correct
3 Correct 7 ms 9736 KB Output is correct
4 Correct 12 ms 9672 KB Output is correct
5 Correct 14 ms 9832 KB Output is correct
6 Correct 31 ms 9928 KB Output is correct
7 Correct 33 ms 10164 KB Output is correct
8 Correct 41 ms 10248 KB Output is correct
9 Correct 63 ms 11132 KB Output is correct
10 Correct 100 ms 11512 KB Output is correct
11 Correct 170 ms 14584 KB Output is correct
12 Correct 174 ms 14784 KB Output is correct
13 Correct 241 ms 87340 KB Output is correct
14 Correct 269 ms 109228 KB Output is correct
15 Runtime error 73 ms 131076 KB Execution killed with signal 9

Subtask #2
15.0 / 85.0

# Verdict Execution time Memory Grader output
1 Runtime error 83 ms 131076 KB Execution killed with signal 9
2 Runtime error 71 ms 131076 KB Execution killed with signal 9
3 Runtime error 79 ms 131076 KB Execution killed with signal 9
4 Correct 299 ms 63720 KB Output is correct
5 Correct 435 ms 78332 KB Output is correct
6 Correct 498 ms 69500 KB Output is correct
7 Runtime error 73 ms 131076 KB Execution killed with signal 9
8 Runtime error 95 ms 131076 KB Execution killed with signal 9
9 Runtime error 102 ms 131072 KB Execution killed with signal 9
10 Runtime error 97 ms 131076 KB Execution killed with signal 9
11 Runtime error 111 ms 131076 KB Execution killed with signal 9
12 Runtime error 107 ms 131076 KB Execution killed with signal 9
13 Runtime error 99 ms 131076 KB Execution killed with signal 9
14 Runtime error 121 ms 131076 KB Execution killed with signal 9
15 Runtime error 109 ms 131076 KB Execution killed with signal 9
16 Runtime error 107 ms 131076 KB Execution killed with signal 9
17 Runtime error 109 ms 131076 KB Execution killed with signal 9