oj.uz

답안 #998272

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
998272 2024-06-13T13:09:30 Z BF001 Regions (IOI09_regions) C++17
0 / 100
 206 ms 77036 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(){
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
        
	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);

	gt.resize(blsiz + 1);
	for(int i = 0; i <= blsiz; i++) gt[i].resize(r + 1);

	init(1);
	for (int i = 1; i <= r; i++){
		if (rg[i].size() < blsiz) continue;
		idx[i] = ++cnt;
		dfs(1, i, 0);
	}

	for (int i = 1; i <= q; i++){
		int r1, r2;
		cin >> r1 >> r2;
		if (rg[r1].size() >= blsiz){
			cout << gt[idx[r1]][r2] << "\n";
			
			continue;
		}
		int res = 0;
		for (auto x : v[r1]){
			res += find(r2, tout[x]) - find(r2, tin[x] - 1);
			break;
		}
		cout << res << "\n";
	}

    return 0;
}

Compilation message

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

Subtask #1
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1 ms 8792 KB Time limit exceeded (wall clock)
2 Execution timed out 2 ms 8792 KB Time limit exceeded (wall clock)
3 Execution timed out 2 ms 8792 KB Time limit exceeded (wall clock)
4 Execution timed out 1 ms 8792 KB Time limit exceeded (wall clock)
5 Execution timed out 1 ms 8792 KB Time limit exceeded (wall clock)
6 Execution timed out 2 ms 8792 KB Time limit exceeded (wall clock)
7 Execution timed out 2 ms 8792 KB Time limit exceeded (wall clock)
8 Execution timed out 2 ms 8792 KB Time limit exceeded (wall clock)
9 Execution timed out 2 ms 9304 KB Time limit exceeded (wall clock)
10 Execution timed out 3 ms 9304 KB Time limit exceeded (wall clock)
11 Execution timed out 4 ms 9560 KB Time limit exceeded (wall clock)
12 Execution timed out 4 ms 10072 KB Time limit exceeded (wall clock)
13 Execution timed out 6 ms 9560 KB Time limit exceeded (wall clock)
14 Execution timed out 10 ms 10072 KB Time limit exceeded (wall clock)
15 Execution timed out 10 ms 13912 KB Time limit exceeded (wall clock)

Subtask #2
0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 39 ms 13400 KB Time limit exceeded (wall clock)
2 Execution timed out 32 ms 11864 KB Time limit exceeded (wall clock)
3 Execution timed out 23 ms 15704 KB Time limit exceeded (wall clock)
4 Execution timed out 8 ms 12888 KB Time limit exceeded (wall clock)
5 Execution timed out 9 ms 15448 KB Time limit exceeded (wall clock)
6 Execution timed out 77 ms 17496 KB Time limit exceeded (wall clock)
7 Execution timed out 98 ms 22608 KB Time limit exceeded (wall clock)
8 Execution timed out 111 ms 31212 KB Time limit exceeded (wall clock)
9 Execution timed out 58 ms 39504 KB Time limit exceeded (wall clock)
10 Execution timed out 206 ms 64852 KB Time limit exceeded (wall clock)
11 Execution timed out 62 ms 60100 KB Time limit exceeded (wall clock)
12 Execution timed out 67 ms 45136 KB Time limit exceeded (wall clock)
13 Execution timed out 82 ms 45908 KB Time limit exceeded (wall clock)
14 Execution timed out 188 ms 53076 KB Time limit exceeded (wall clock)
15 Execution timed out 63 ms 67976 KB Time limit exceeded (wall clock)
16 Execution timed out 67 ms 77036 KB Time limit exceeded (wall clock)
17 Execution timed out 102 ms 66384 KB Time limit exceeded (wall clock)