oj.uz

Submission #493131

# Submission time Handle Problem Language Result Execution time Memory
493131 2021-12-10T06:27:49 Z flappybird Regions (IOI09_regions) C++14
29 / 100
 597 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 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;
	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 'long long int'} and 'std::vector<long long 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
14.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9672 KB Output is correct
2 Correct 5 ms 9636 KB Output is correct
3 Correct 8 ms 9800 KB Output is correct
4 Correct 11 ms 9784 KB Output is correct
5 Correct 14 ms 9820 KB Output is correct
6 Correct 28 ms 10076 KB Output is correct
7 Correct 22 ms 10184 KB Output is correct
8 Correct 42 ms 10368 KB Output is correct
9 Correct 68 ms 11292 KB Output is correct
10 Correct 114 ms 11828 KB Output is correct
11 Correct 168 ms 15260 KB Output is correct
12 Correct 190 ms 15204 KB Output is correct
13 Correct 255 ms 87928 KB Output is correct
14 Correct 268 ms 109724 KB Output is correct
15 Runtime error 70 ms 131076 KB Execution killed with signal 9

Subtask #2
15.0 / 85.0

# Verdict Execution time Memory Grader output
1 Runtime error 78 ms 131076 KB Execution killed with signal 9
2 Runtime error 76 ms 131076 KB Execution killed with signal 9
3 Runtime error 74 ms 131076 KB Execution killed with signal 9
4 Correct 318 ms 64464 KB Output is correct
5 Correct 458 ms 79700 KB Output is correct
6 Correct 597 ms 70920 KB Output is correct
7 Runtime error 87 ms 131076 KB Execution killed with signal 9
8 Runtime error 87 ms 131072 KB Execution killed with signal 9
9 Runtime error 98 ms 131076 KB Execution killed with signal 9
10 Runtime error 101 ms 131076 KB Execution killed with signal 9
11 Runtime error 131 ms 131076 KB Execution killed with signal 9
12 Runtime error 128 ms 131076 KB Execution killed with signal 9
13 Runtime error 99 ms 131076 KB Execution killed with signal 9
14 Runtime error 107 ms 131076 KB Execution killed with signal 9
15 Runtime error 119 ms 131076 KB Execution killed with signal 9
16 Runtime error 113 ms 131076 KB Execution killed with signal 9
17 Runtime error 105 ms 131076 KB Execution killed with signal 9