oj.uz

Submission #53618

# Submission time Handle Problem Language Result Execution time Memory
53618 2018-06-30T14:06:11 Z baactree Regions (IOI09_regions) C++17
0 / 100
 2382 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, [&](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 {
			return 0;
			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 7 ms 6392 KB Output isn't correct
2 Incorrect 9 ms 6580 KB Output isn't correct
3 Incorrect 10 ms 6660 KB Output isn't correct
4 Incorrect 13 ms 6712 KB Output isn't correct
5 Incorrect 14 ms 6864 KB Output isn't correct
6 Incorrect 17 ms 8120 KB Output isn't correct
7 Incorrect 29 ms 8120 KB Output isn't correct
8 Incorrect 22 ms 8120 KB Output isn't correct
9 Incorrect 62 ms 9244 KB Output isn't correct
10 Incorrect 109 ms 10424 KB Output isn't correct
11 Incorrect 117 ms 10424 KB Output isn't correct
12 Incorrect 144 ms 11964 KB Output isn't correct
13 Incorrect 116 ms 11964 KB Output isn't correct
14 Incorrect 179 ms 11964 KB Output isn't correct
15 Incorrect 227 ms 15548 KB Output isn't correct

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 617 ms 17244 KB Output isn't correct
2 Incorrect 857 ms 17244 KB Output isn't correct
3 Incorrect 1430 ms 20800 KB Output isn't correct
4 Incorrect 110 ms 20800 KB Unexpected end of file - int32 expected
5 Incorrect 261 ms 25148 KB Unexpected end of file - int32 expected
6 Incorrect 199 ms 29260 KB Unexpected end of file - int32 expected
7 Incorrect 317 ms 37592 KB Unexpected end of file - int32 expected
8 Incorrect 850 ms 45684 KB Unexpected end of file - int32 expected
9 Incorrect 1666 ms 57936 KB Unexpected end of file - int32 expected
10 Incorrect 1855 ms 83536 KB Unexpected end of file - int32 expected
11 Incorrect 2123 ms 83536 KB Unexpected end of file - int32 expected
12 Incorrect 1985 ms 83536 KB Unexpected end of file - int32 expected
13 Incorrect 1895 ms 83536 KB Unexpected end of file - int32 expected
14 Incorrect 2025 ms 83536 KB Unexpected end of file - int32 expected
15 Incorrect 2382 ms 85228 KB Unexpected end of file - int32 expected
16 Incorrect 2303 ms 94356 KB Unexpected end of file - int32 expected
17 Incorrect 2258 ms 94356 KB Unexpected end of file - int32 expected