oj.uz

Submission #53631

# Submission time Handle Problem Language Result Execution time Memory
53631 2018-06-30T14:57:21 Z baactree Regions (IOI09_regions) C++17
80 / 100
 7477 ms 131072 KB 
#include <bits/stdc++.h>
using namespace std;
int n, r, q;
vector<int> adj[200005];
int arr[200005];
const int sz = 1000;
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 83 ms 104324 KB Output is correct
2 Correct 83 ms 104376 KB Output is correct
3 Correct 83 ms 104452 KB Output is correct
4 Correct 88 ms 104452 KB Output is correct
5 Correct 94 ms 104504 KB Output is correct
6 Correct 110 ms 104528 KB Output is correct
7 Correct 91 ms 104656 KB Output is correct
8 Correct 98 ms 104712 KB Output is correct
9 Correct 129 ms 105224 KB Output is correct
10 Correct 162 ms 105224 KB Output is correct
11 Correct 238 ms 105524 KB Output is correct
12 Correct 284 ms 106168 KB Output is correct
13 Correct 259 ms 106168 KB Output is correct
14 Correct 325 ms 106572 KB Output is correct
15 Correct 377 ms 110140 KB Output is correct

Subtask #2
65.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1389 ms 110156 KB Output is correct
2 Correct 1886 ms 110156 KB Output is correct
3 Correct 2663 ms 112552 KB Output is correct
4 Correct 340 ms 112552 KB Output is correct
5 Correct 433 ms 112552 KB Output is correct
6 Correct 623 ms 112552 KB Output is correct
7 Correct 900 ms 112552 KB Output is correct
8 Correct 1268 ms 116028 KB Output is correct
9 Correct 2574 ms 116028 KB Output is correct
10 Correct 4987 ms 122368 KB Output is correct
11 Correct 5512 ms 122368 KB Output is correct
12 Correct 4872 ms 122368 KB Output is correct
13 Correct 6261 ms 122368 KB Output is correct
14 Execution timed out 7477 ms 122368 KB Time limit exceeded (wall clock)
15 Execution timed out 7339 ms 122604 KB Time limit exceeded (wall clock)
16 Execution timed out 7035 ms 131072 KB Time limit exceeded (wall clock)
17 Execution timed out 7054 ms 131072 KB Time limit exceeded (wall clock)