oj.uz

Submission #493122

# Submission time Handle Problem Language Result Execution time Memory
493122 2021-12-10T06:09:08 Z flappybird Regions (IOI09_regions) C++17
10 / 100
 583 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 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 '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 6 ms 9672 KB Output is correct
3 Correct 8 ms 9672 KB Output is correct
4 Correct 6 ms 9748 KB Output is correct
5 Correct 14 ms 9852 KB Output is correct
6 Correct 22 ms 10112 KB Output is correct
7 Correct 36 ms 10192 KB Output is correct
8 Correct 43 ms 10304 KB Output is correct
9 Correct 61 ms 11352 KB Output is correct
10 Correct 126 ms 19912 KB Output is correct
11 Incorrect 151 ms 76608 KB Output isn't correct
12 Runtime error 59 ms 131076 KB Execution killed with signal 9
13 Runtime error 61 ms 131076 KB Execution killed with signal 9
14 Incorrect 176 ms 109692 KB Output isn't correct
15 Runtime error 71 ms 131072 KB Execution killed with signal 9

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Runtime error 78 ms 131076 KB Execution killed with signal 9
2 Runtime error 75 ms 131076 KB Execution killed with signal 9
3 Runtime error 77 ms 131076 KB Execution killed with signal 9
4 Incorrect 259 ms 64644 KB Output isn't correct
5 Runtime error 59 ms 131076 KB Execution killed with signal 9
6 Incorrect 583 ms 70816 KB Output isn't correct
7 Runtime error 73 ms 131076 KB Execution killed with signal 9
8 Runtime error 80 ms 131076 KB Execution killed with signal 9
9 Runtime error 98 ms 131076 KB Execution killed with signal 9
10 Runtime error 91 ms 131076 KB Execution killed with signal 9
11 Runtime error 103 ms 131076 KB Execution killed with signal 9
12 Runtime error 102 ms 131076 KB Execution killed with signal 9
13 Runtime error 103 ms 131076 KB Execution killed with signal 9
14 Runtime error 125 ms 131076 KB Execution killed with signal 9
15 Runtime error 113 ms 131076 KB Execution killed with signal 9
16 Runtime error 106 ms 131076 KB Execution killed with signal 9
17 Runtime error 103 ms 131076 KB Execution killed with signal 9