oj.uz

Submission #493140

# Submission time Handle Problem Language Result Execution time Memory
493140 2021-12-10T06:34:14 Z flappybird Regions (IOI09_regions) C++17
60 / 100
 8000 ms 131076 KB 
#include <bits/stdc++.h>
#include <unordered_map>
#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 200
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;
	unordered_map<ll, bool> chk;
	unordered_map<ll, long long> val;
	dfs(1);
	for (i = 1; i <= Q; i++) {
		cin >> a >> b;
		if (chk[a * 25001 + b]) cout << val[a * 25001 + 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 * 25001 + b] = 1;
			val[a * 25001 + b] = ans;
			cout << ans << endl;
		}
	}
}

Compilation message

regions.cpp: In function 'void dfs(ll, ll)':
regions.cpp:32:20: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |   for (ll i = 0; i < bdp[x].size(); i++) bdp[x][i] += bdp[v][i];
      |                  ~~^~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9672 KB Output is correct
2 Correct 7 ms 9632 KB Output is correct
3 Correct 12 ms 9724 KB Output is correct
4 Correct 12 ms 9740 KB Output is correct
5 Correct 13 ms 9848 KB Output is correct
6 Correct 22 ms 9920 KB Output is correct
7 Correct 36 ms 10128 KB Output is correct
8 Correct 44 ms 10208 KB Output is correct
9 Correct 59 ms 11044 KB Output is correct
10 Correct 120 ms 11456 KB Output is correct
11 Correct 168 ms 11976 KB Output is correct
12 Correct 216 ms 13308 KB Output is correct
13 Correct 306 ms 13236 KB Output is correct
14 Correct 653 ms 13804 KB Output is correct
15 Correct 576 ms 21152 KB Output is correct

Subtask #2
45.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1164 ms 81748 KB Output is correct
2 Correct 1014 ms 125352 KB Output is correct
3 Runtime error 80 ms 131076 KB Execution killed with signal 9
4 Correct 363 ms 15072 KB Output is correct
5 Correct 449 ms 18536 KB Output is correct
6 Correct 586 ms 44104 KB Output is correct
7 Correct 828 ms 53832 KB Output is correct
8 Correct 861 ms 112712 KB Output is correct
9 Runtime error 108 ms 131076 KB Execution killed with signal 9
10 Runtime error 101 ms 131076 KB Execution killed with signal 9
11 Runtime error 111 ms 131076 KB Execution killed with signal 9
12 Runtime error 113 ms 131076 KB Execution killed with signal 9
13 Runtime error 106 ms 131076 KB Execution killed with signal 9
14 Correct 4314 ms 97544 KB Output is correct
15 Execution timed out 8074 ms 60424 KB Time limit exceeded
16 Runtime error 112 ms 131076 KB Execution killed with signal 9
17 Correct 5963 ms 118796 KB Output is correct