oj.uz

Submission #53616

# Submission time Handle Problem Language Result Execution time Memory
53616 2018-06-30T13:59:58 Z baactree Regions (IOI09_regions) C++17
0 / 100
 4403 ms 94356 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);
	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]]++;
	}
	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 {
			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:54: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 12 ms 6520 KB Output isn't correct
2 Incorrect 11 ms 6584 KB Output isn't correct
3 Incorrect 17 ms 6660 KB Output isn't correct
4 Incorrect 20 ms 6708 KB Output isn't correct
5 Incorrect 23 ms 6836 KB Output isn't correct
6 Incorrect 39 ms 8000 KB Output isn't correct
7 Incorrect 35 ms 8000 KB Output isn't correct
8 Incorrect 38 ms 8000 KB Output isn't correct
9 Incorrect 118 ms 9264 KB Output isn't correct
10 Incorrect 175 ms 10248 KB Output isn't correct
11 Incorrect 144 ms 10248 KB Output isn't correct
12 Incorrect 202 ms 11912 KB Output isn't correct
13 Incorrect 191 ms 11912 KB Output isn't correct
14 Incorrect 166 ms 11912 KB Output isn't correct
15 Incorrect 217 ms 15548 KB Output isn't correct

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 981 ms 17212 KB Output isn't correct
2 Incorrect 1051 ms 17212 KB Output isn't correct
3 Incorrect 1010 ms 20796 KB Output isn't correct
4 Incorrect 337 ms 20796 KB Output isn't correct
5 Incorrect 689 ms 25020 KB Output isn't correct
6 Incorrect 826 ms 29244 KB Output isn't correct
7 Incorrect 1004 ms 37688 KB Output isn't correct
8 Incorrect 1937 ms 45808 KB Output isn't correct
9 Incorrect 2993 ms 57916 KB Output isn't correct
10 Incorrect 3799 ms 83356 KB Output isn't correct
11 Incorrect 4403 ms 83356 KB Output isn't correct
12 Incorrect 2964 ms 83356 KB Output isn't correct
13 Incorrect 3214 ms 83356 KB Output isn't correct
14 Incorrect 3515 ms 83356 KB Output isn't correct
15 Incorrect 4172 ms 85400 KB Output isn't correct
16 Incorrect 4062 ms 94356 KB Output isn't correct
17 Incorrect 3967 ms 94356 KB Output isn't correct