oj.uz

Submission #293343

# Submission time Handle Problem Language Result Execution time Memory
293343 2020-09-07T22:59:53 Z Plurm Regions (IOI09_regions) C++11
100 / 100
 5546 ms 117588 KB 
#include <bits/stdc++.h>
using namespace std;
const int K = 2000;
vector<int> sp; // special regions
vector<int> bckt[25005];
int h[200005];
int s[200005];
int stat[200005][200005/K+10];
int cnt[200005]; // how many parents with i-th region
vector<int> g[200005];
int prec[200005/K+10][25005]; // prec[i][j] -> how the i-th special regions manage ones from j-th region
vector<int> et;
vector<int> etbckt[25005];
int st[200005];
int ft[200005];
void dfs(int u){
	st[u] = et.size();
	etbckt[h[u]].push_back(et.size());
	et.push_back(u);
	for(int i = 0; i < sp.size(); i++){
		stat[u][i] = cnt[sp[i]];
	}
	cnt[h[u]]++;
	for(int v : g[u]){
		dfs(v);
	}
	cnt[h[u]]--;
	ft[u] = et.size();
}
int query(int r1, int r2){
	if(binary_search(sp.begin(), sp.end(), r1)){
		// special region
		return prec[lower_bound(sp.begin(), sp.end(), r1)-sp.begin()][r2];
	}else{
		// normal region
		int ans = 0;
		for(int x : bckt[r1]){
			int l = st[x];
			int r = ft[x];
			ans += lower_bound(etbckt[r2].begin(), etbckt[r2].end(), r) - lower_bound(etbckt[r2].begin(), etbckt[r2].end(), l);
		}
		return ans;
	}
}
int main(){
	int n, r, q;
	scanf("%d%d%d",&n,&r,&q);
	scanf("%d", h+1);
	bckt[h[1]].push_back(1);
	for(int i = 2; i <= n; i++){
		scanf("%d%d", s+i, h+i);
		g[s[i]].push_back(i);
		bckt[h[i]].push_back(i);
	}
	for(int i = 1; i <= r; i++){
		if(bckt[i].size() > K){
			sp.push_back(i);
		}
	}
	dfs(1);
	for(int i = 1; i <= r; i++){
		for(int u : bckt[i]){
			for(int j = 0; j < sp.size(); j++){
				prec[j][i] += stat[u][j];
			}
		}
	}
	while(q--){
		int r1, r2;
		scanf("%d%d",&r1,&r2);
		printf("%d\n", query(r1, r2));
		fflush(stdout);
	}
	return 0;
}

Compilation message

regions.cpp: In function 'void dfs(int)':
regions.cpp:20:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |  for(int i = 0; i < sp.size(); i++){
      |                 ~~^~~~~~~~~~~
regions.cpp: In function 'int main()':
regions.cpp:63:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |    for(int j = 0; j < sp.size(); j++){
      |                   ~~^~~~~~~~~~~
regions.cpp:47:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   47 |  scanf("%d%d%d",&n,&r,&q);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~
regions.cpp:48:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   48 |  scanf("%d", h+1);
      |  ~~~~~^~~~~~~~~~~
regions.cpp:51:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   51 |   scanf("%d%d", s+i, h+i);
      |   ~~~~~^~~~~~~~~~~~~~~~~~
regions.cpp:70:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   70 |   scanf("%d%d",&r1,&r2);
      |   ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6272 KB Output is correct
2 Correct 4 ms 6272 KB Output is correct
3 Correct 6 ms 6272 KB Output is correct
4 Correct 7 ms 6272 KB Output is correct
5 Correct 13 ms 6272 KB Output is correct
6 Correct 23 ms 6272 KB Output is correct
7 Correct 35 ms 6272 KB Output is correct
8 Correct 37 ms 6400 KB Output is correct
9 Correct 49 ms 7040 KB Output is correct
10 Correct 89 ms 6912 KB Output is correct
11 Correct 146 ms 7168 KB Output is correct
12 Correct 149 ms 7904 KB Output is correct
13 Correct 205 ms 7424 KB Output is correct
14 Correct 284 ms 8064 KB Output is correct
15 Correct 309 ms 11252 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 2330 ms 44016 KB Output is correct
2 Correct 2868 ms 44784 KB Output is correct
3 Correct 3564 ms 52848 KB Output is correct
4 Correct 293 ms 8184 KB Output is correct
5 Correct 473 ms 10368 KB Output is correct
6 Correct 1607 ms 9592 KB Output is correct
7 Correct 2235 ms 11124 KB Output is correct
8 Correct 1575 ms 17008 KB Output is correct
9 Correct 2741 ms 17520 KB Output is correct
10 Correct 5284 ms 23408 KB Output is correct
11 Correct 5546 ms 17260 KB Output is correct
12 Correct 1914 ms 100464 KB Output is correct
13 Correct 2201 ms 100844 KB Output is correct
14 Correct 3417 ms 104940 KB Output is correct
15 Correct 3780 ms 110444 KB Output is correct
16 Correct 3582 ms 117588 KB Output is correct
17 Correct 4144 ms 115944 KB Output is correct