oj.uz

Submission #493132

# Submission time Handle Problem Language Result Execution time Memory
493132 2021-12-10T06:28:22 Z flappybird Regions (IOI09_regions) C++14
40 / 100
 1204 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 100
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 6 ms 9672 KB Output is correct
3 Correct 7 ms 9672 KB Output is correct
4 Correct 10 ms 9732 KB Output is correct
5 Correct 13 ms 9820 KB Output is correct
6 Correct 28 ms 10048 KB Output is correct
7 Correct 32 ms 10184 KB Output is correct
8 Correct 44 ms 10244 KB Output is correct
9 Correct 54 ms 11244 KB Output is correct
10 Correct 108 ms 11656 KB Output is correct
11 Correct 184 ms 12320 KB Output is correct
12 Correct 207 ms 13440 KB Output is correct
13 Correct 307 ms 13768 KB Output is correct
14 Correct 220 ms 62144 KB Output is correct
15 Correct 298 ms 95580 KB Output is correct

Subtask #2
25.0 / 85.0

# Verdict Execution time Memory Grader output
1 Runtime error 74 ms 131076 KB Execution killed with signal 9
2 Correct 1204 ms 126436 KB Output is correct
3 Runtime error 78 ms 131076 KB Execution killed with signal 9
4 Correct 284 ms 40408 KB Output is correct
5 Correct 506 ms 35004 KB Output is correct
6 Correct 632 ms 45508 KB Output is correct
7 Correct 929 ms 74476 KB Output is correct
8 Runtime error 76 ms 131076 KB Execution killed with signal 9
9 Runtime error 95 ms 131076 KB Execution killed with signal 9
10 Runtime error 102 ms 131076 KB Execution killed with signal 9
11 Runtime error 112 ms 131076 KB Execution killed with signal 9
12 Runtime error 119 ms 131076 KB Execution killed with signal 9
13 Runtime error 115 ms 131076 KB Execution killed with signal 9
14 Runtime error 112 ms 131076 KB Execution killed with signal 9
15 Runtime error 112 ms 131076 KB Execution killed with signal 9
16 Runtime error 130 ms 131076 KB Execution killed with signal 9
17 Runtime error 135 ms 131076 KB Execution killed with signal 9