oj.uz

Submission #534323

# Submission time Handle Problem Language Result Execution time Memory
534323 2022-03-08T04:41:01 Z Cantfindme Regions (IOI09_regions) C++17
55 / 100
 3156 ms 28288 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int> pi;
#define f first
#define s second
#define FAST ios_base::sync_with_stdio(0); cin.tie(0);
#define all(x) x.begin(),x.end()

const int maxn = 100010;
const int INF = LLONG_MAX/2;
const int mod = 1e9+7;
const int len = 450;

int n, R, Q;
vector <int> adjlist[maxn];
vector <int> v[maxn], v2[maxn];
int ans[len+10][maxn];
int indx[maxn], rev[maxn], col[maxn];

int pre[maxn], post[maxn];

int co = 1;
void dfs(int x, int p) {
	pre[x] = co++;
	rev[pre[x]] = x;
	for (auto i: adjlist[x]) if (i != p) {
		dfs(i,x);
	}
	post[x] = co - 1;

}

int32_t main() {
	// ifstream cin("input.txt");

	cin >> n >> R >> Q;
	for (int i =1;i<=n;i++) {
		if (i == 1) {
			int x; cin >> x;
			col[i] = x;
			v[x].push_back(i);
		} else {
			int x, p; cin >> p >> x;
			col[i] = x;
			v[x].push_back(i);
			adjlist[p].push_back(i);
		}
	}
	dfs(1,-1);

	co = 0;
	for (int x = 1; x <= R; x++) {
		for (auto i: v[x]) {
			v2[x].push_back(pre[i]);
		}
		sort(all(v2[x]));

		if (v[x].size() >= len) {
			indx[x] = co; 
			vector <int> pref(n+2, 0);
			for (auto i: v[x]) {
				pref[pre[i]]++;
				pref[post[i]+1]--;
			}

			int cur = 0;
			for (int j = 1; j<= n;j++) {
				cur += pref[j];
				int child = rev[j];
				ans[indx[x]][col[child]] += cur;
			}

			co++;
		}
	}

	for (int q=0;q<Q;q++) {
		int r1, r2; cin >> r1 >> r2;
		if (v[r1].size() >= len) {
			cout << ans[indx[r1]][r2] << "\n";
		} else {
			int rans = 0;
			for (auto i: v[r1]) { //sqrt(N)
				int lb = lower_bound(all(v2[r2]), pre[i]) - v2[r2].begin();
				int rb = upper_bound(all(v2[r2]), post[i]) - v2[r2].begin();
				rans += rb - lb;
			}
			cout << rans << "\n";
		}
	}
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7240 KB Output is correct
2 Correct 4 ms 7240 KB Output is correct
3 Correct 6 ms 7368 KB Output is correct
4 Correct 9 ms 7368 KB Output is correct
5 Correct 12 ms 7368 KB Output is correct
6 Correct 22 ms 7368 KB Output is correct
7 Correct 37 ms 7368 KB Output is correct
8 Correct 40 ms 7496 KB Output is correct
9 Correct 60 ms 8008 KB Output is correct
10 Correct 68 ms 8056 KB Output is correct
11 Correct 123 ms 8520 KB Output is correct
12 Correct 165 ms 9288 KB Output is correct
13 Correct 222 ms 9144 KB Output is correct
14 Correct 353 ms 9928 KB Output is correct
15 Correct 202 ms 12608 KB Output is correct

Subtask #2
40.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1817 ms 14968 KB Output is correct
2 Correct 2245 ms 14080 KB Output is correct
3 Correct 3156 ms 17096 KB Output is correct
4 Correct 301 ms 9920 KB Output is correct
5 Correct 287 ms 11688 KB Output is correct
6 Correct 571 ms 15868 KB Output is correct
7 Correct 1296 ms 15100 KB Output is correct
8 Correct 1165 ms 28288 KB Output is correct
9 Runtime error 91 ms 24788 KB Execution killed with signal 6
10 Runtime error 85 ms 25432 KB Execution killed with signal 11
11 Runtime error 107 ms 23452 KB Execution killed with signal 6
12 Runtime error 96 ms 24896 KB Execution killed with signal 11
13 Runtime error 79 ms 24476 KB Execution killed with signal 11
14 Runtime error 76 ms 24196 KB Execution killed with signal 11
15 Runtime error 78 ms 25308 KB Execution killed with signal 11
16 Runtime error 82 ms 25284 KB Execution killed with signal 11
17 Runtime error 76 ms 25200 KB Execution killed with signal 11