oj.uz

Submission #293341

# Submission time Handle Problem Language Result Execution time Memory
293341 2020-09-07T22:56:55 Z Plurm Regions (IOI09_regions) C++11
55 / 100
 5432 ms 131076 KB 
#include <bits/stdc++.h>
using namespace std;
const int K = 500;
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 9 ms 6272 KB Output is correct
5 Correct 9 ms 6272 KB Output is correct
6 Correct 21 ms 6272 KB Output is correct
7 Correct 31 ms 6272 KB Output is correct
8 Correct 39 ms 6400 KB Output is correct
9 Correct 42 ms 6912 KB Output is correct
10 Correct 79 ms 7032 KB Output is correct
11 Correct 133 ms 7168 KB Output is correct
12 Correct 125 ms 7928 KB Output is correct
13 Correct 174 ms 7416 KB Output is correct
14 Correct 340 ms 8064 KB Output is correct
15 Correct 297 ms 11252 KB Output is correct

Subtask #2
40.0 / 85.0

# Verdict Execution time Memory Grader output
1 Runtime error 112 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Runtime error 102 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 Runtime error 98 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
4 Correct 369 ms 8192 KB Output is correct
5 Correct 502 ms 10368 KB Output is correct
6 Correct 1766 ms 9600 KB Output is correct
7 Correct 2187 ms 11124 KB Output is correct
8 Correct 1536 ms 17008 KB Output is correct
9 Correct 2719 ms 17520 KB Output is correct
10 Correct 5394 ms 23404 KB Output is correct
11 Correct 5432 ms 17388 KB Output is correct
12 Runtime error 168 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
13 Runtime error 166 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
14 Runtime error 179 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
15 Runtime error 151 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
16 Runtime error 148 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
17 Runtime error 166 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)