oj.uz

Submission #493126

# Submission time Handle Problem Language Result Execution time Memory
493126 2021-12-10T06:15:17 Z flappybird Regions (IOI09_regions) C++14
10 / 100
 1100 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 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);
	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 '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 5 ms 9672 KB Output is correct
3 Correct 6 ms 9728 KB Output is correct
4 Correct 9 ms 9812 KB Output is correct
5 Correct 17 ms 9824 KB Output is correct
6 Correct 28 ms 10072 KB Output is correct
7 Correct 38 ms 10204 KB Output is correct
8 Correct 45 ms 10212 KB Output is correct
9 Correct 61 ms 11444 KB Output is correct
10 Correct 103 ms 11568 KB Output is correct
11 Incorrect 175 ms 13760 KB Output isn't correct
12 Incorrect 220 ms 14788 KB Output isn't correct
13 Incorrect 242 ms 50456 KB Output isn't correct
14 Incorrect 231 ms 62416 KB Output isn't correct
15 Incorrect 231 ms 95692 KB Output isn't correct

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Runtime error 69 ms 131076 KB Execution killed with signal 9
2 Incorrect 1100 ms 126232 KB Output isn't correct
3 Runtime error 74 ms 131076 KB Execution killed with signal 9
4 Incorrect 339 ms 40408 KB Output isn't correct
5 Incorrect 492 ms 50136 KB Output isn't correct
6 Incorrect 705 ms 45608 KB Output isn't correct
7 Incorrect 954 ms 83264 KB Output isn't correct
8 Runtime error 82 ms 131076 KB Execution killed with signal 9
9 Runtime error 101 ms 131076 KB Execution killed with signal 9
10 Runtime error 92 ms 131076 KB Execution killed with signal 9
11 Runtime error 106 ms 131076 KB Execution killed with signal 9
12 Runtime error 103 ms 131076 KB Execution killed with signal 9
13 Runtime error 104 ms 131076 KB Execution killed with signal 9
14 Runtime error 108 ms 131076 KB Execution killed with signal 9
15 Runtime error 115 ms 131076 KB Execution killed with signal 9
16 Runtime error 106 ms 131076 KB Execution killed with signal 9
17 Runtime error 105 ms 131076 KB Execution killed with signal 9