oj.uz

Submission #53629

# Submission time Handle Problem Language Result Execution time Memory
53629 2018-06-30T14:51:07 Z baactree Regions (IOI09_regions) C++17
80 / 100
 7513 ms 79328 KB 
#include <bits/stdc++.h>
using namespace std;
int n, r, q;
vector<int> adj[200005];
int arr[200005];
const int sz = 467;
int cache[sz][25005];
pair<int,int> cnt[25005];
int inv[25005];
int le[200005], ri[200005];
vector<int> idx[25005];
vector<pair<int, int> > vec[25005];
int vn;
void dfs(int now, int par) {
	idx[arr[now]].push_back(vn);
	le[now] = vn++;
	for (auto &there : adj[now]) {
		if (there == par)continue;
		dfs(there, now);
	}
	ri[now] = vn++;
	vec[arr[now]].emplace_back(le[now], ri[now]);
}
int solve(int r1, int r2) {
	int &ret = cache[inv[r1]][r2];
	if (ret != -1) return ret;
	ret = 0;
	for (auto x : vec[r1]) {
		int le = x.first;
		int ri = x.second;
		ret += upper_bound(idx[r2].begin(), idx[r2].end(), ri) - lower_bound(idx[r2].begin(), idx[r2].end(), le);
	}
	return ret;
}
int main() {
	scanf("%d%d%d", &n, &r, &q);
	scanf("%d", &arr[1]);
	cnt[arr[1]].first++;
	for (int i = 2; i <= n; i++) {
		int a, b;
		scanf("%d%d", &a, &b);
		adj[a].push_back(i);
		adj[i].push_back(a);
		arr[i] = b;
		cnt[arr[i]].first++;
	}
	for (int i = 0; i < 25005; i++)
		cnt[i].second = i;
	sort(cnt, cnt + 25005, [&](pair<int, int> &a, pair<int, int> &b) {
		return a > b;
	});
	for (int i = 0; i < 25005; i++)
		inv[cnt[i].second] = i;
	dfs(1, 0);
	memset(cache, -1, sizeof(cache));
	while (q--) {
		int a, b;
		scanf("%d%d", &a, &b);
		if (inv[a] < sz) {
			printf("%d\n", solve(a,b));
			fflush(stdout);
		}
		else {
			int ans = 0;
			for (auto x : vec[a]) {
				int le = x.first;
				int ri = x.second;
				ans += upper_bound(idx[b].begin(), idx[b].end(), ri) - lower_bound(idx[b].begin(), idx[b].end(), le);
			}
			printf("%d\n", ans);
			fflush(stdout);
		}
	}
	return 0;
}

Compilation message

regions.cpp: In function 'int main()':
regions.cpp:36:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d", &n, &r, &q);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
regions.cpp:37:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &arr[1]);
  ~~~~~^~~~~~~~~~~~~~~
regions.cpp:41:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &a, &b);
   ~~~~~^~~~~~~~~~~~~~~~
regions.cpp:58:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &a, &b);
   ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 52088 KB Output is correct
2 Correct 54 ms 52276 KB Output is correct
3 Correct 48 ms 52276 KB Output is correct
4 Correct 52 ms 52276 KB Output is correct
5 Correct 50 ms 52380 KB Output is correct
6 Correct 57 ms 52540 KB Output is correct
7 Correct 74 ms 52540 KB Output is correct
8 Correct 83 ms 52540 KB Output is correct
9 Correct 92 ms 53036 KB Output is correct
10 Correct 150 ms 53036 KB Output is correct
11 Correct 205 ms 53292 KB Output is correct
12 Correct 249 ms 53932 KB Output is correct
13 Correct 202 ms 53932 KB Output is correct
14 Correct 278 ms 54316 KB Output is correct
15 Correct 329 ms 58028 KB Output is correct

Subtask #2
65.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1311 ms 58028 KB Output is correct
2 Correct 1809 ms 58028 KB Output is correct
3 Correct 2769 ms 60332 KB Output is correct
4 Correct 337 ms 60332 KB Output is correct
5 Correct 422 ms 60332 KB Output is correct
6 Correct 618 ms 60332 KB Output is correct
7 Correct 872 ms 60332 KB Output is correct
8 Correct 1419 ms 63952 KB Output is correct
9 Correct 2374 ms 63952 KB Output is correct
10 Correct 4625 ms 70232 KB Output is correct
11 Correct 5618 ms 70232 KB Output is correct
12 Correct 4696 ms 70232 KB Output is correct
13 Correct 6104 ms 70232 KB Output is correct
14 Execution timed out 7378 ms 70232 KB Time limit exceeded (wall clock)
15 Execution timed out 7513 ms 70320 KB Time limit exceeded (wall clock)
16 Execution timed out 7410 ms 79328 KB Time limit exceeded (wall clock)
17 Execution timed out 7262 ms 79328 KB Time limit exceeded (wall clock)