oj.uz

Submission #293342

# Submission time Handle Problem Language Result Execution time Memory
293342 2020-09-07T22:58:29 Z Plurm Regions (IOI09_regions) C++11
70 / 100
 6186 ms 131076 KB 
#include <bits/stdc++.h>
using namespace std;
const int K = 1000;
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 8 ms 6272 KB Output is correct
5 Correct 9 ms 6272 KB Output is correct
6 Correct 19 ms 6272 KB Output is correct
7 Correct 34 ms 6272 KB Output is correct
8 Correct 35 ms 6400 KB Output is correct
9 Correct 48 ms 6912 KB Output is correct
10 Correct 87 ms 6912 KB Output is correct
11 Correct 145 ms 7168 KB Output is correct
12 Correct 146 ms 7928 KB Output is correct
13 Correct 192 ms 7424 KB Output is correct
14 Correct 341 ms 8064 KB Output is correct
15 Correct 313 ms 11252 KB Output is correct

Subtask #2
55.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 2083 ms 73328 KB Output is correct
2 Correct 2443 ms 76144 KB Output is correct
3 Correct 3263 ms 87920 KB Output is correct
4 Correct 315 ms 8192 KB Output is correct
5 Correct 379 ms 10368 KB Output is correct
6 Correct 1678 ms 9592 KB Output is correct
7 Correct 1885 ms 11124 KB Output is correct
8 Correct 1488 ms 17008 KB Output is correct
9 Correct 2895 ms 17520 KB Output is correct
10 Correct 4930 ms 23404 KB Output is correct
11 Correct 6186 ms 17260 KB Output is correct
12 Runtime error 164 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
13 Runtime error 154 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
14 Runtime error 174 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
15 Runtime error 149 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
16 Runtime error 157 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
17 Runtime error 165 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)