oj.uz

Submission #493124

# Submission time Handle Problem Language Result Execution time Memory
493124 2021-12-10T06:12:01 Z flappybird Regions (IOI09_regions) C++14
21 / 100
 939 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 50
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 += (long long)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 += (long long)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
11.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9672 KB Output is correct
2 Correct 6 ms 9672 KB Output is correct
3 Correct 8 ms 9736 KB Output is correct
4 Correct 11 ms 9672 KB Output is correct
5 Correct 12 ms 9788 KB Output is correct
6 Correct 24 ms 10088 KB Output is correct
7 Correct 39 ms 10092 KB Output is correct
8 Correct 30 ms 10328 KB Output is correct
9 Correct 68 ms 11276 KB Output is correct
10 Correct 100 ms 11636 KB Output is correct
11 Incorrect 144 ms 37704 KB Output isn't correct
12 Correct 164 ms 30992 KB Output is correct
13 Incorrect 183 ms 78344 KB Output isn't correct
14 Incorrect 228 ms 62160 KB Output isn't correct
15 Incorrect 282 ms 95808 KB Output isn't correct

Subtask #2
10.0 / 85.0

# Verdict Execution time Memory Grader output
1 Runtime error 73 ms 131076 KB Execution killed with signal 9
2 Runtime error 290 ms 131076 KB Execution killed with signal 9
3 Runtime error 78 ms 131076 KB Execution killed with signal 9
4 Incorrect 293 ms 40404 KB Output isn't correct
5 Correct 474 ms 96476 KB Output is correct
6 Incorrect 625 ms 45448 KB Output isn't correct
7 Correct 939 ms 87420 KB Output is correct
8 Runtime error 94 ms 131076 KB Execution killed with signal 9
9 Runtime error 98 ms 131076 KB Execution killed with signal 9
10 Runtime error 98 ms 131076 KB Execution killed with signal 9
11 Runtime error 118 ms 131076 KB Execution killed with signal 9
12 Runtime error 108 ms 131076 KB Execution killed with signal 9
13 Runtime error 109 ms 131076 KB Execution killed with signal 9
14 Runtime error 117 ms 131072 KB Execution killed with signal 9
15 Runtime error 108 ms 131076 KB Execution killed with signal 9
16 Runtime error 107 ms 131076 KB Execution killed with signal 9
17 Runtime error 106 ms 131076 KB Execution killed with signal 9