oj.uz

Submission #53619

# Submission time Handle Problem Language Result Execution time Memory
53619 2018-06-30T14:08:46 Z baactree Regions (IOI09_regions) C++17
0 / 100
 8000 ms 94448 KB 
#include <bits/stdc++.h>
using namespace std;
int n, r, q;
vector<int> adj[200005];
int arr[200005];
const int sz = 505;
int dp[sz][25005];
pair<int,int> cnt[25005];
int inv[25005];
bitset<sz> bs[200005];
int le[200005], ri[200005];
vector<int> idx[25005];
vector<pair<int, int> > vec[25005];
int vn;
void dfs(int now, int par) {
	if (inv[arr[now]] < sz)bs[now][inv[arr[now]]] = 1;
	bs[now] |= bs[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++;
	if (inv[arr[now]] >= sz) 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 = 1; i <= n; i++) {
		for (int j = 0; j < sz; j++)
			if (bs[i][j])dp[j][arr[i]]++;
	}
	for (int i = 0; i < 25005; i++)
		sort(vec[i].begin(), vec[i].end());
	while (q--) {
		int a, b;
		scanf("%d%d", &a, &b);
		if (inv[a] < sz) {
			printf("%d\n", dp[inv[a]][b]);
			fflush(stdout);
		}
		else {
			while (true);
			int pre = -1;
			int ans = 0;
			for (auto x : vec[a]) {
				int le = x.first;
				int ri = x.second;
				if (le <= pre)continue;
				ans += upper_bound(idx[b].begin(), idx[b].end(), ri) - lower_bound(idx[b].begin(), idx[b].end(), le);
				pre = ri;
			}
			printf("%d\n", ans);
			fflush(stdout);
		}
	}
	return 0;
}

Compilation message

regions.cpp: In function 'int main()':
regions.cpp:28: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:29:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &arr[1]);
  ~~~~~^~~~~~~~~~~~~~~
regions.cpp:33: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:56: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
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 6392 KB Output isn't correct
2 Incorrect 10 ms 6580 KB Output isn't correct
3 Incorrect 9 ms 6660 KB Output isn't correct
4 Incorrect 14 ms 6696 KB Output isn't correct
5 Incorrect 15 ms 6872 KB Output isn't correct
6 Incorrect 22 ms 8152 KB Output isn't correct
7 Incorrect 27 ms 8152 KB Output isn't correct
8 Incorrect 39 ms 8152 KB Output isn't correct
9 Incorrect 57 ms 9204 KB Output isn't correct
10 Incorrect 82 ms 10280 KB Output isn't correct
11 Incorrect 122 ms 10280 KB Output isn't correct
12 Incorrect 168 ms 11916 KB Output isn't correct
13 Incorrect 166 ms 11916 KB Output isn't correct
14 Incorrect 134 ms 11916 KB Output isn't correct
15 Incorrect 218 ms 15476 KB Output isn't correct

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 859 ms 17196 KB Output isn't correct
2 Incorrect 858 ms 17196 KB Output isn't correct
3 Incorrect 1304 ms 20876 KB Output isn't correct
4 Execution timed out 8061 ms 20876 KB Time limit exceeded
5 Execution timed out 8079 ms 25168 KB Time limit exceeded
6 Execution timed out 8023 ms 29068 KB Time limit exceeded
7 Execution timed out 8103 ms 37396 KB Time limit exceeded
8 Execution timed out 8087 ms 45648 KB Time limit exceeded
9 Execution timed out 8064 ms 57936 KB Time limit exceeded
10 Execution timed out 8087 ms 83464 KB Time limit exceeded
11 Execution timed out 8064 ms 83464 KB Time limit exceeded
12 Execution timed out 8066 ms 83464 KB Time limit exceeded
13 Execution timed out 8015 ms 83464 KB Time limit exceeded
14 Execution timed out 8083 ms 83464 KB Time limit exceeded
15 Execution timed out 8048 ms 85380 KB Time limit exceeded
16 Execution timed out 8086 ms 94448 KB Time limit exceeded
17 Execution timed out 8067 ms 94448 KB Time limit exceeded