oj.uz

Submission #493123

# Submission time Handle Problem Language Result Execution time Memory
493123 2021-12-10T06:10:18 Z flappybird Regions (IOI09_regions) C++14
15 / 100
 954 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 30
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);
	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
10.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9672 KB Output is correct
2 Correct 7 ms 9672 KB Output is correct
3 Correct 7 ms 9672 KB Output is correct
4 Correct 9 ms 9672 KB Output is correct
5 Correct 13 ms 9820 KB Output is correct
6 Correct 23 ms 10012 KB Output is correct
7 Correct 41 ms 10184 KB Output is correct
8 Correct 47 ms 10284 KB Output is correct
9 Correct 63 ms 11432 KB Output is correct
10 Correct 95 ms 15684 KB Output is correct
11 Incorrect 99 ms 44332 KB Output isn't correct
12 Incorrect 171 ms 84360 KB Output isn't correct
13 Incorrect 221 ms 78272 KB Output isn't correct
14 Incorrect 223 ms 62080 KB Output isn't correct
15 Incorrect 268 ms 95664 KB Output isn't correct

Subtask #2
5.0 / 85.0

# Verdict Execution time Memory Grader output
1 Runtime error 80 ms 131076 KB Execution killed with signal 9
2 Runtime error 87 ms 131076 KB Execution killed with signal 9
3 Runtime error 81 ms 131076 KB Execution killed with signal 9
4 Incorrect 319 ms 40436 KB Output isn't correct
5 Runtime error 73 ms 131076 KB Execution killed with signal 9
6 Incorrect 705 ms 45472 KB Output isn't correct
7 Correct 954 ms 94132 KB Output is correct
8 Runtime error 79 ms 131076 KB Execution killed with signal 9
9 Runtime error 93 ms 131076 KB Execution killed with signal 9
10 Runtime error 103 ms 131076 KB Execution killed with signal 9
11 Runtime error 110 ms 131072 KB Execution killed with signal 9
12 Runtime error 107 ms 131076 KB Execution killed with signal 9
13 Runtime error 109 ms 131076 KB Execution killed with signal 9
14 Runtime error 104 ms 131076 KB Execution killed with signal 9
15 Runtime error 125 ms 131076 KB Execution killed with signal 9
16 Runtime error 109 ms 131076 KB Execution killed with signal 9
17 Runtime error 112 ms 131076 KB Execution killed with signal 9