oj.uz

Submission #493133

# Submission time Handle Problem Language Result Execution time Memory
493133 2021-12-10T06:28:54 Z flappybird Regions (IOI09_regions) C++14
60 / 100
 8000 ms 131076 KB 
#include <bits/stdc++.h>
#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 200
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;
	map<pll, bool> chk;
	map<pll, long long> val;
	dfs(1);
	for (i = 1; i <= Q; i++) {
		cin >> a >> b;
		if (chk[{a, b}]) cout << val[{a, 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, b}] = 1;
			val[{a, b}] = ans;
			cout << ans << endl;
		}
	}
}

Compilation message

regions.cpp: In function 'void dfs(ll, ll)':
regions.cpp:31:20: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |   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 5 ms 9672 KB Output is correct
2 Correct 5 ms 9672 KB Output is correct
3 Correct 10 ms 9724 KB Output is correct
4 Correct 10 ms 9672 KB Output is correct
5 Correct 13 ms 9812 KB Output is correct
6 Correct 14 ms 10032 KB Output is correct
7 Correct 44 ms 10088 KB Output is correct
8 Correct 45 ms 10284 KB Output is correct
9 Correct 61 ms 11268 KB Output is correct
10 Correct 95 ms 11632 KB Output is correct
11 Correct 151 ms 12352 KB Output is correct
12 Correct 206 ms 13528 KB Output is correct
13 Correct 283 ms 13664 KB Output is correct
14 Correct 623 ms 14232 KB Output is correct
15 Correct 616 ms 21692 KB Output is correct

Subtask #2
45.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1308 ms 82740 KB Output is correct
2 Correct 1156 ms 126336 KB Output is correct
3 Runtime error 84 ms 131076 KB Execution killed with signal 9
4 Correct 291 ms 15940 KB Output is correct
5 Correct 397 ms 20028 KB Output is correct
6 Correct 581 ms 45416 KB Output is correct
7 Correct 907 ms 54644 KB Output is correct
8 Correct 1184 ms 115580 KB Output is correct
9 Runtime error 93 ms 131076 KB Execution killed with signal 9
10 Runtime error 108 ms 131076 KB Execution killed with signal 9
11 Runtime error 126 ms 131076 KB Execution killed with signal 9
12 Runtime error 102 ms 131076 KB Execution killed with signal 9
13 Runtime error 119 ms 131076 KB Execution killed with signal 9
14 Correct 4304 ms 103392 KB Output is correct
15 Execution timed out 8053 ms 67524 KB Time limit exceeded
16 Runtime error 110 ms 131076 KB Execution killed with signal 9
17 Correct 5815 ms 123724 KB Output is correct