Submission #998278

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
998278	2024-06-13T13:32:22 Z	BF001	Regions (IOI09_regions)	C++17	0 / 100	192 ms	34128 KB

regions

#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);
 
	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;
		cout << "0\n";
	}
 
    return 0;
} 

Compilation message

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

Subtask #1

0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	1 ms	8792 KB	Time limit exceeded (wall clock)
2	Execution timed out	1 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	2 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	1 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	9300 KB	Time limit exceeded (wall clock)
10	Execution timed out	3 ms	9048 KB	Time limit exceeded (wall clock)
11	Execution timed out	4 ms	9304 KB	Time limit exceeded (wall clock)
12	Execution timed out	5 ms	9816 KB	Time limit exceeded (wall clock)
13	Execution timed out	5 ms	9560 KB	Time limit exceeded (wall clock)
14	Execution timed out	9 ms	10072 KB	Time limit exceeded (wall clock)
15	Execution timed out	9 ms	13656 KB	Time limit exceeded (wall clock)

Subtask #2

0 / 85.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	40 ms	13148 KB	Time limit exceeded (wall clock)
2	Execution timed out	46 ms	11564 KB	Time limit exceeded (wall clock)
3	Execution timed out	22 ms	15444 KB	Time limit exceeded (wall clock)
4	Execution timed out	8 ms	10072 KB	Time limit exceeded (wall clock)
5	Execution timed out	11 ms	11608 KB	Time limit exceeded (wall clock)
6	Execution timed out	73 ms	12924 KB	Time limit exceeded (wall clock)
7	Execution timed out	89 ms	14072 KB	Time limit exceeded (wall clock)
8	Execution timed out	99 ms	22864 KB	Time limit exceeded (wall clock)
9	Execution timed out	30 ms	16728 KB	Time limit exceeded (wall clock)
10	Execution timed out	192 ms	34128 KB	Time limit exceeded (wall clock)
11	Execution timed out	40 ms	16208 KB	Time limit exceeded (wall clock)
12	Execution timed out	52 ms	17976 KB	Time limit exceeded (wall clock)
13	Execution timed out	63 ms	18632 KB	Time limit exceeded (wall clock)
14	Execution timed out	192 ms	19536 KB	Time limit exceeded (wall clock)
15	Execution timed out	42 ms	24400 KB	Time limit exceeded (wall clock)
16	Execution timed out	50 ms	33360 KB	Time limit exceeded (wall clock)
17	Execution timed out	83 ms	33108 KB	Time limit exceeded (wall clock)