oj.uz

Submission #53617

# Submission time Handle Problem Language Result Execution time Memory
53617 2018-06-30T14:02:24 Z baactree Regions (IOI09_regions) C++17
0 / 100
 8000 ms 94376 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 {
			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: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 Execution timed out 8087 ms 6520 KB Time limit exceeded
2 Execution timed out 8087 ms 6520 KB Time limit exceeded
3 Execution timed out 8096 ms 6520 KB Time limit exceeded
4 Incorrect 16 ms 6768 KB Unexpected end of file - int32 expected
5 Incorrect 13 ms 6820 KB Unexpected end of file - int32 expected
6 Execution timed out 8074 ms 8152 KB Time limit exceeded
7 Incorrect 41 ms 8152 KB Unexpected end of file - int32 expected
8 Incorrect 43 ms 8152 KB Unexpected end of file - int32 expected
9 Incorrect 49 ms 9396 KB Unexpected end of file - int32 expected
10 Incorrect 97 ms 10480 KB Unexpected end of file - int32 expected
11 Incorrect 176 ms 10480 KB Unexpected end of file - int32 expected
12 Incorrect 150 ms 12092 KB Unexpected end of file - int32 expected
13 Incorrect 188 ms 12092 KB Unexpected end of file - int32 expected
14 Incorrect 129 ms 12092 KB Unexpected end of file - int32 expected
15 Incorrect 283 ms 15676 KB Unexpected end of file - int32 expected

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 892 ms 17212 KB Unexpected end of file - int32 expected
2 Incorrect 857 ms 17212 KB Unexpected end of file - int32 expected
3 Incorrect 1265 ms 20796 KB Unexpected end of file - int32 expected
4 Execution timed out 8069 ms 20796 KB Time limit exceeded
5 Execution timed out 8013 ms 25036 KB Time limit exceeded
6 Execution timed out 8084 ms 29416 KB Time limit exceeded
7 Execution timed out 8080 ms 37488 KB Time limit exceeded
8 Execution timed out 8068 ms 45856 KB Time limit exceeded
9 Execution timed out 8080 ms 58060 KB Time limit exceeded
10 Execution timed out 8077 ms 83532 KB Time limit exceeded
11 Execution timed out 8063 ms 83532 KB Time limit exceeded
12 Execution timed out 8085 ms 83532 KB Time limit exceeded
13 Execution timed out 8064 ms 83532 KB Time limit exceeded
14 Execution timed out 8016 ms 83532 KB Time limit exceeded
15 Execution timed out 8055 ms 85236 KB Time limit exceeded
16 Execution timed out 8071 ms 94376 KB Time limit exceeded
17 Execution timed out 8032 ms 94376 KB Time limit exceeded