oj.uz

Submission #998293

# Submission time Handle Problem Language Result Execution time Memory
998293 2024-06-13T14:13:21 Z BF001 Regions (IOI09_regions) C++17
100 / 100
 2757 ms 34128 KB 
#include <bits/stdc++.h>
using namespace std;
 
#define N 200005
#define M 25005 
 
int n, r, q, h[N], tin[N], tout[N], tim, idx[N], cnt = -1, blsiz;
vector<int> adj[N], rg[M], v[M];
vector<vector<int>> gt;
 
void init(int u){
	tin[u] = ++tim;
	rg[h[u]].push_back(tin[u]);
	v[h[u]].push_back(u);
	for (auto x : adj[u]){
		init(x);
	}
	tout[u] = tim;
}
 
void dfs(int u, int typ, int cnt){
	int ncnt = cnt;
	if (h[u] == typ) ncnt++;
	for (auto x : adj[u]){
		gt[idx[typ]][h[x]] += ncnt;
		dfs(x, typ, ncnt);
	} 	
}
 
int find(int typ, int val){
	int l = 0, r = rg[typ].size() - 1, rt = 0;
	while (l <= r){
		int mid = (l + r) >> 1;
		if (rg[typ][mid] <= val){
			rt = mid + 1;
			l = mid + 1;
		}
		else r = mid - 1; 
	}
	return rt;
}
 
signed main(){
        
	cin >> n >> r >> q;
	cin >> h[1];
	for (int i = 2; i <= n; i++){
		int p;
		cin >> p >> h[i];
		adj[p].push_back(i);
	}   
 
	blsiz = sqrt(n);
 
	init(1);
	for (int i = 1; i <= r; i++){
		if (rg[i].size() < blsiz) continue;
		gt.push_back(vector<int> (r + 1));
		idx[i] = ++cnt;
		dfs(1, i, 0);
	}
 
	while (q--){
		int r1, r2;
		cin >> r1 >> r2;
		if (rg[r1].size() >= blsiz){
			cout << gt[idx[r1]][r2] << endl;
			continue;
		}
		int res = 0;
		for (auto x : v[r1]){
			res += find(r2, tout[x]) - find(r2, tin[x] - 1);
		}
		cout << res << endl;
	}
 
    return 0;
}

Compilation message

regions.cpp: In function 'int main()':
regions.cpp:57:20: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   57 |   if (rg[i].size() < blsiz) continue;
      |       ~~~~~~~~~~~~~^~~~~~~
regions.cpp:66:21: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   66 |   if (rg[r1].size() >= blsiz){
      |       ~~~~~~~~~~~~~~^~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8792 KB Output is correct
2 Correct 1 ms 8792 KB Output is correct
3 Correct 2 ms 8792 KB Output is correct
4 Correct 3 ms 8792 KB Output is correct
5 Correct 5 ms 8792 KB Output is correct
6 Correct 11 ms 8792 KB Output is correct
7 Correct 17 ms 8792 KB Output is correct
8 Correct 19 ms 8792 KB Output is correct
9 Correct 26 ms 9304 KB Output is correct
10 Correct 52 ms 9048 KB Output is correct
11 Correct 80 ms 9304 KB Output is correct
12 Correct 97 ms 9816 KB Output is correct
13 Correct 113 ms 9560 KB Output is correct
14 Correct 189 ms 10072 KB Output is correct
15 Correct 189 ms 13656 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1438 ms 13184 KB Output is correct
2 Correct 1653 ms 11352 KB Output is correct
3 Correct 2142 ms 15508 KB Output is correct
4 Correct 206 ms 10072 KB Output is correct
5 Correct 266 ms 11608 KB Output is correct
6 Correct 504 ms 12880 KB Output is correct
7 Correct 924 ms 14160 KB Output is correct
8 Correct 859 ms 22608 KB Output is correct
9 Correct 1650 ms 16724 KB Output is correct
10 Correct 2335 ms 34128 KB Output is correct
11 Correct 2757 ms 16208 KB Output is correct
12 Correct 1014 ms 18012 KB Output is correct
13 Correct 1417 ms 18508 KB Output is correct
14 Correct 1748 ms 19536 KB Output is correct
15 Correct 2384 ms 24656 KB Output is correct
16 Correct 2386 ms 33360 KB Output is correct
17 Correct 2110 ms 33012 KB Output is correct