oj.uz

Submission #493127

# Submission time Handle Problem Language Result Execution time Memory
493127 2021-12-10T06:17:36 Z flappybird Regions (IOI09_regions) C++17
0 / 100
 17 ms 19528 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[i] = 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
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 12 ms 19440 KB Execution killed with signal 11
2 Runtime error 13 ms 19488 KB Execution killed with signal 11
3 Runtime error 13 ms 19400 KB Execution killed with signal 11
4 Runtime error 14 ms 19400 KB Execution killed with signal 11
5 Runtime error 13 ms 19520 KB Execution killed with signal 11
6 Runtime error 14 ms 19496 KB Execution killed with signal 11
7 Runtime error 13 ms 19428 KB Execution killed with signal 11
8 Runtime error 13 ms 19508 KB Execution killed with signal 11
9 Runtime error 15 ms 19400 KB Execution killed with signal 11
10 Runtime error 14 ms 19424 KB Execution killed with signal 11
11 Runtime error 14 ms 19528 KB Execution killed with signal 11
12 Runtime error 14 ms 19400 KB Execution killed with signal 11
13 Runtime error 13 ms 19400 KB Execution killed with signal 11
14 Runtime error 17 ms 19492 KB Execution killed with signal 11
15 Runtime error 12 ms 19400 KB Execution killed with signal 11

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Runtime error 12 ms 19400 KB Execution killed with signal 11
2 Runtime error 13 ms 19476 KB Execution killed with signal 11
3 Runtime error 15 ms 19432 KB Execution killed with signal 11
4 Runtime error 13 ms 19400 KB Execution killed with signal 11
5 Runtime error 13 ms 19424 KB Execution killed with signal 11
6 Runtime error 13 ms 19428 KB Execution killed with signal 11
7 Runtime error 13 ms 19528 KB Execution killed with signal 11
8 Runtime error 13 ms 19520 KB Execution killed with signal 11
9 Runtime error 14 ms 19444 KB Execution killed with signal 11
10 Runtime error 13 ms 19500 KB Execution killed with signal 11
11 Runtime error 13 ms 19400 KB Execution killed with signal 11
12 Runtime error 13 ms 19400 KB Execution killed with signal 11
13 Runtime error 13 ms 19400 KB Execution killed with signal 11
14 Runtime error 13 ms 19400 KB Execution killed with signal 11
15 Runtime error 13 ms 19440 KB Execution killed with signal 11
16 Runtime error 13 ms 19400 KB Execution killed with signal 11
17 Runtime error 13 ms 19400 KB Execution killed with signal 11