oj.uz

Submission #53628

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

Compilation message

regions.cpp: In function 'int main()':
regions.cpp:54:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while (lidx < idx[b].size() && idx[b][lidx] < le)lidx++;
            ~~~~~^~~~~~~~~~~~~~~
regions.cpp:55:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while (ridx < idx[b].size() && idx[b][ridx] <= ri)ridx++;
            ~~~~~^~~~~~~~~~~~~~~
regions.cpp:25: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:26:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &arr[1]);
  ~~~~~^~~~~~~~~~~~~~~
regions.cpp:30: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:63: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
3.0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 14 ms 8312 KB Output isn't correct
2 Incorrect 13 ms 8500 KB Output isn't correct
3 Incorrect 14 ms 8580 KB Output isn't correct
4 Incorrect 14 ms 8656 KB Output isn't correct
5 Incorrect 18 ms 8680 KB Output isn't correct
6 Correct 37 ms 9112 KB Output is correct
7 Incorrect 43 ms 9112 KB Output isn't correct
8 Incorrect 45 ms 9148 KB Output isn't correct
9 Correct 75 ms 9888 KB Output is correct
10 Incorrect 140 ms 9992 KB Output isn't correct
11 Incorrect 176 ms 10044 KB Output isn't correct
12 Incorrect 269 ms 11044 KB Output isn't correct
13 Incorrect 268 ms 11044 KB Output isn't correct
14 Incorrect 240 ms 11044 KB Output isn't correct
15 Correct 238 ms 14696 KB Output is correct

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 761 ms 14696 KB Output isn't correct
2 Incorrect 999 ms 14696 KB Output isn't correct
3 Incorrect 1484 ms 17140 KB Output isn't correct
4 Incorrect 507 ms 18096 KB Output isn't correct
5 Incorrect 886 ms 22244 KB Output isn't correct
6 Incorrect 1275 ms 25180 KB Output isn't correct
7 Incorrect 1964 ms 32036 KB Output isn't correct
8 Incorrect 2859 ms 38604 KB Output isn't correct
9 Incorrect 5774 ms 47536 KB Output isn't correct
10 Execution timed out 8029 ms 70436 KB Time limit exceeded
11 Execution timed out 8020 ms 70436 KB Time limit exceeded
12 Incorrect 6569 ms 70436 KB Unexpected end of file - int32 expected
13 Incorrect 6715 ms 70436 KB Unexpected end of file - int32 expected
14 Execution timed out 8018 ms 70436 KB Time limit exceeded
15 Execution timed out 8069 ms 70436 KB Time limit exceeded
16 Execution timed out 8055 ms 75436 KB Time limit exceeded
17 Execution timed out 8010 ms 75436 KB Time limit exceeded