oj.uz

답안 #53622

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
53622 2018-06-30T14:33:44 Z baactree Regions (IOI09_regions) C++17
50 / 100
 8000 ms 40580 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) {
		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 = 0; i < sz; i++) {
		int a = cnt[i].second;
		for (int b = 1; b <= r; b++) {
			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);
			}
			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: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:59: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
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 8312 KB Output is correct
2 Correct 13 ms 8500 KB Output is correct
3 Correct 14 ms 8576 KB Output is correct
4 Correct 13 ms 8636 KB Output is correct
5 Correct 20 ms 8712 KB Output is correct
6 Correct 29 ms 9096 KB Output is correct
7 Correct 44 ms 9096 KB Output is correct
8 Correct 53 ms 9100 KB Output is correct
9 Correct 118 ms 9868 KB Output is correct
10 Correct 241 ms 10176 KB Output is correct
11 Correct 289 ms 10176 KB Output is correct
12 Correct 700 ms 11236 KB Output is correct
13 Correct 485 ms 11236 KB Output is correct
14 Correct 550 ms 11236 KB Output is correct
15 Correct 662 ms 14700 KB Output is correct

Subtask #2
35.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1532 ms 14780 KB Output is correct
2 Correct 1868 ms 14780 KB Output is correct
3 Correct 2590 ms 17340 KB Output is correct
4 Correct 1247 ms 18172 KB Output is correct
5 Correct 2138 ms 22104 KB Output is correct
6 Correct 3455 ms 25180 KB Output is correct
7 Correct 5211 ms 32108 KB Output is correct
8 Execution timed out 8039 ms 38676 KB Time limit exceeded
9 Execution timed out 8086 ms 38676 KB Time limit exceeded
10 Execution timed out 8077 ms 38676 KB Time limit exceeded
11 Execution timed out 8100 ms 38676 KB Time limit exceeded
12 Execution timed out 8055 ms 38676 KB Time limit exceeded
13 Execution timed out 8067 ms 38676 KB Time limit exceeded
14 Execution timed out 8086 ms 38676 KB Time limit exceeded
15 Execution timed out 8087 ms 38676 KB Time limit exceeded
16 Execution timed out 8035 ms 40580 KB Time limit exceeded
17 Execution timed out 8009 ms 40580 KB Time limit exceeded