oj.uz

Submission #53614

# Submission time Handle Problem Language Result Execution time Memory
53614 2018-06-30T13:43:36 Z baactree Regions (IOI09_regions) C++17
0 / 100
 4970 ms 87220 KB 
#include <bits/stdc++.h>
using namespace std;
int n, r, q;
vector<int> adj[200005];
int arr[200005];
const int sz = 447;
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);
	reverse(cnt,cnt + 25005);
	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]]++;
	}
	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 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:52: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 10 ms 6520 KB Output isn't correct
2 Incorrect 10 ms 6520 KB Output isn't correct
3 Incorrect 12 ms 6772 KB Output isn't correct
4 Incorrect 13 ms 6908 KB Output isn't correct
5 Incorrect 15 ms 6908 KB Output isn't correct
6 Incorrect 24 ms 8172 KB Output isn't correct
7 Incorrect 35 ms 8172 KB Output isn't correct
8 Incorrect 26 ms 8172 KB Output isn't correct
9 Incorrect 73 ms 9248 KB Output isn't correct
10 Incorrect 89 ms 10272 KB Output isn't correct
11 Incorrect 130 ms 10272 KB Output isn't correct
12 Incorrect 115 ms 11936 KB Output isn't correct
13 Incorrect 150 ms 11936 KB Output isn't correct
14 Incorrect 169 ms 11936 KB Output isn't correct
15 Incorrect 283 ms 15292 KB Output isn't correct

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 804 ms 16672 KB Output isn't correct
2 Incorrect 775 ms 16672 KB Output isn't correct
3 Incorrect 1339 ms 20120 KB Output isn't correct
4 Incorrect 343 ms 20120 KB Output isn't correct
5 Incorrect 500 ms 23376 KB Output isn't correct
6 Incorrect 470 ms 27128 KB Output isn't correct
7 Incorrect 1209 ms 34380 KB Output isn't correct
8 Incorrect 1872 ms 42572 KB Output isn't correct
9 Incorrect 2926 ms 53452 KB Output isn't correct
10 Incorrect 3704 ms 76648 KB Output isn't correct
11 Incorrect 4970 ms 76648 KB Output isn't correct
12 Incorrect 2571 ms 76648 KB Output isn't correct
13 Incorrect 3169 ms 76648 KB Output isn't correct
14 Incorrect 3547 ms 76648 KB Output isn't correct
15 Incorrect 3934 ms 78188 KB Output isn't correct
16 Incorrect 3693 ms 87220 KB Output isn't correct
17 Incorrect 3297 ms 87220 KB Output isn't correct