oj.uz

Submission #493130

# Submission time Handle Problem Language Result Execution time Memory
493130 2021-12-10T06:23:51 Z flappybird Regions (IOI09_regions) C++14
10 / 100
 614 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[rrr[b]] != -1) {
					for (auto x : rr[a]) ans += bdp[x][num[rrr[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[rrr[a]] != -1) {
					for (auto x : rr[b]) ans += tdp[x][num[rrr[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
10.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9672 KB Output is correct
2 Correct 5 ms 9672 KB Output is correct
3 Correct 7 ms 9740 KB Output is correct
4 Correct 9 ms 9784 KB Output is correct
5 Correct 15 ms 9812 KB Output is correct
6 Correct 16 ms 10112 KB Output is correct
7 Correct 27 ms 10208 KB Output is correct
8 Correct 53 ms 10432 KB Output is correct
9 Correct 57 ms 11352 KB Output is correct
10 Correct 110 ms 11856 KB Output is correct
11 Incorrect 209 ms 14920 KB Output isn't correct
12 Incorrect 244 ms 15100 KB Output isn't correct
13 Incorrect 301 ms 87848 KB Output isn't correct
14 Incorrect 268 ms 109680 KB Output isn't correct
15 Runtime error 73 ms 131076 KB Execution killed with signal 9

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Runtime error 79 ms 131076 KB Execution killed with signal 9
2 Runtime error 82 ms 131076 KB Execution killed with signal 9
3 Runtime error 71 ms 131076 KB Execution killed with signal 9
4 Incorrect 354 ms 64644 KB Output isn't correct
5 Incorrect 496 ms 79820 KB Output isn't correct
6 Incorrect 614 ms 71004 KB Output isn't correct
7 Runtime error 104 ms 131076 KB Execution killed with signal 9
8 Runtime error 85 ms 131076 KB Execution killed with signal 9
9 Runtime error 111 ms 131076 KB Execution killed with signal 9
10 Runtime error 118 ms 131076 KB Execution killed with signal 9
11 Runtime error 109 ms 131076 KB Execution killed with signal 9
12 Runtime error 104 ms 131076 KB Execution killed with signal 9
13 Runtime error 118 ms 131076 KB Execution killed with signal 9
14 Runtime error 114 ms 131076 KB Execution killed with signal 9
15 Runtime error 106 ms 131076 KB Execution killed with signal 9
16 Runtime error 106 ms 131076 KB Execution killed with signal 9
17 Runtime error 102 ms 131076 KB Execution killed with signal 9