oj.uz

Submission #53624

# Submission time Handle Problem Language Result Execution time Memory
53624 2018-06-30T14:38:35 Z baactree Regions (IOI09_regions) C++17
50 / 100
 8000 ms 56824 KB 
#include <bits/stdc++.h>
using namespace std;
int n, r, q;
vector<int> adj[200005];
int arr[200005];
const int sz = 1000;
int dp[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 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) {
		if (a.first == b.first)return a.second < b.second;
		return a.first > b.first;
	});
	for (int i = 0; i < 25005; i++)
		inv[cnt[i].second] = i;
	dfs(1, 0);
	for (int i = 0; i < sz; i++) {
		int a = cnt[i].second;
		for (int b = 1; b <= r; b++) {
			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);
			}
			dp[i][b] = ans;
		}
	}
	while (q--) {
		int a, b;
		scanf("%d%d", &a, &b);
		if (inv[a] < sz) {
			printf("%d\n", dp[inv[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:25: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:26:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &arr[1]);
  ~~~~~^~~~~~~~~~~~~~~
regions.cpp:30: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:59: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 11 ms 10616 KB Output is correct
2 Correct 12 ms 10680 KB Output is correct
3 Correct 13 ms 10732 KB Output is correct
4 Correct 14 ms 10912 KB Output is correct
5 Correct 22 ms 10972 KB Output is correct
6 Correct 23 ms 11864 KB Output is correct
7 Correct 46 ms 11864 KB Output is correct
8 Correct 36 ms 11864 KB Output is correct
9 Correct 88 ms 12764 KB Output is correct
10 Correct 173 ms 13156 KB Output is correct
11 Correct 260 ms 13156 KB Output is correct
12 Correct 606 ms 14304 KB Output is correct
13 Correct 503 ms 14304 KB Output is correct
14 Correct 595 ms 14304 KB Output is correct
15 Correct 590 ms 17628 KB Output is correct

Subtask #2
35.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1774 ms 17628 KB Output is correct
2 Correct 1994 ms 17628 KB Output is correct
3 Correct 2421 ms 19948 KB Output is correct
4 Correct 1532 ms 28540 KB Output is correct
5 Correct 2926 ms 34700 KB Output is correct
6 Correct 3659 ms 41892 KB Output is correct
7 Correct 5965 ms 54916 KB Output is correct
8 Execution timed out 8060 ms 56824 KB Time limit exceeded
9 Execution timed out 8085 ms 56824 KB Time limit exceeded
10 Execution timed out 8005 ms 56824 KB Time limit exceeded
11 Execution timed out 8055 ms 56824 KB Time limit exceeded
12 Execution timed out 8086 ms 56824 KB Time limit exceeded
13 Execution timed out 8058 ms 56824 KB Time limit exceeded
14 Execution timed out 8073 ms 56824 KB Time limit exceeded
15 Execution timed out 8015 ms 56824 KB Time limit exceeded
16 Execution timed out 8102 ms 56824 KB Time limit exceeded
17 Execution timed out 8083 ms 56824 KB Time limit exceeded