oj.uz

Submission #53630

# Submission time Handle Problem Language Result Execution time Memory
53630 2018-06-30T14:56:46 Z baactree Regions (IOI09_regions) C++17
80 / 100
 7212 ms 92348 KB 
#include <bits/stdc++.h>
using namespace std;
int n, r, q;
vector<int> adj[200005];
int arr[200005];
const int sz = 600;
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 60 ms 65272 KB Output is correct
2 Correct 62 ms 65292 KB Output is correct
3 Correct 61 ms 65380 KB Output is correct
4 Correct 63 ms 65380 KB Output is correct
5 Correct 65 ms 65424 KB Output is correct
6 Correct 73 ms 65528 KB Output is correct
7 Correct 84 ms 65528 KB Output is correct
8 Correct 74 ms 65592 KB Output is correct
9 Correct 100 ms 66132 KB Output is correct
10 Correct 168 ms 66132 KB Output is correct
11 Correct 207 ms 66340 KB Output is correct
12 Correct 247 ms 66980 KB Output is correct
13 Correct 267 ms 66980 KB Output is correct
14 Correct 361 ms 67388 KB Output is correct
15 Correct 368 ms 71100 KB Output is correct

Subtask #2
65.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1551 ms 71100 KB Output is correct
2 Correct 1742 ms 71100 KB Output is correct
3 Correct 2613 ms 73584 KB Output is correct
4 Correct 307 ms 73584 KB Output is correct
5 Correct 407 ms 73584 KB Output is correct
6 Correct 700 ms 73584 KB Output is correct
7 Correct 707 ms 73584 KB Output is correct
8 Correct 1243 ms 76956 KB Output is correct
9 Correct 2374 ms 76956 KB Output is correct
10 Correct 4365 ms 83292 KB Output is correct
11 Correct 4994 ms 83292 KB Output is correct
12 Correct 5021 ms 83292 KB Output is correct
13 Correct 5977 ms 83292 KB Output is correct
14 Execution timed out 7101 ms 83292 KB Time limit exceeded (wall clock)
15 Execution timed out 7212 ms 83432 KB Time limit exceeded (wall clock)
16 Execution timed out 6848 ms 92348 KB Time limit exceeded (wall clock)
17 Execution timed out 6911 ms 92348 KB Time limit exceeded (wall clock)