oj.uz

Submission #493125

# Submission time Handle Problem Language Result Execution time Memory
493125 2021-12-10T06:12:50 Z flappybird Regions (IOI09_regions) C++14
17 / 100
 683 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);
	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
12.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 9740 KB Output is correct
4 Correct 9 ms 9748 KB Output is correct
5 Correct 14 ms 9872 KB Output is correct
6 Correct 26 ms 10116 KB Output is correct
7 Correct 35 ms 10164 KB Output is correct
8 Correct 44 ms 10372 KB Output is correct
9 Correct 51 ms 11248 KB Output is correct
10 Correct 112 ms 11956 KB Output is correct
11 Correct 152 ms 14912 KB Output is correct
12 Correct 206 ms 15096 KB Output is correct
13 Incorrect 242 ms 87880 KB Output isn't correct
14 Incorrect 228 ms 109700 KB Output isn't correct
15 Runtime error 68 ms 131076 KB Execution killed with signal 9

Subtask #2
5.0 / 85.0

# Verdict Execution time Memory Grader output
1 Runtime error 71 ms 131076 KB Execution killed with signal 9
2 Runtime error 77 ms 131076 KB Execution killed with signal 9
3 Runtime error 83 ms 131076 KB Execution killed with signal 9
4 Incorrect 300 ms 64500 KB Output isn't correct
5 Correct 419 ms 79844 KB Output is correct
6 Incorrect 683 ms 71004 KB Output isn't correct
7 Runtime error 79 ms 131076 KB Execution killed with signal 9
8 Runtime error 87 ms 131076 KB Execution killed with signal 9
9 Runtime error 97 ms 131076 KB Execution killed with signal 9
10 Runtime error 111 ms 131076 KB Execution killed with signal 9
11 Runtime error 104 ms 131076 KB Execution killed with signal 9
12 Runtime error 109 ms 131076 KB Execution killed with signal 9
13 Runtime error 108 ms 131076 KB Execution killed with signal 9
14 Runtime error 108 ms 131076 KB Execution killed with signal 9
15 Runtime error 127 ms 131076 KB Execution killed with signal 9
16 Runtime error 108 ms 131076 KB Execution killed with signal 9
17 Runtime error 108 ms 131076 KB Execution killed with signal 9