Submission #998288

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
998288	2024-06-13T14:07:39 Z	BF001	Regions (IOI09_regions)	C++17	0 / 100	53 ms	25348 KB

regions

#include <bits/stdc++.h>
using namespace std;

#define N 200005
#define M 25005

int n, r, q, tim, tin[N], tout[N], vs[M], node[N], h[N], idx[M], cnt = -1;
vector<int> adj[N], rg[M];
unordered_map<int, int> gt[M];

void init(int u, int p){
	tin[u] = ++tim;
	for (auto x : adj[u]){
		if (x == p) continue;
		init(x, u);
	}
	tout[u] = tim;
}

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);
    }

    init(1, 0);
    const int blsiz = sqrt(n);

    for (int i = 1; i <= n; i++){
    	if (vs[h[node[i]]]) continue;
    	vs[h[node[i]]] = 1;
    	if (rg[h[node[i]]].size() <= blsiz) continue;
    	vector<int> pre(n + 2, 0);
    	for (auto x : rg[h[node[i]]]){
    		int l = tin[node[x]], r = tout[node[x]];
    		pre[l]++; pre[r + 1]--;
    	}
    	for (int j = 1; j <= n; j++){
    		pre[j] += pre[j - 1];
    		gt[h[node[i]]][h[node[j]]] += pre[j];  
    	}
    }

    while (q--){
    	int r1, r2;
    	cin >> r1 >> r2;
    	cout << 0 << "\n";
    }

    return 0;
}     

Compilation message

regions.cpp: In function 'int main()':
regions.cpp:52:32: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'const int' [-Wsign-compare]
   52 |      if (rg[h[node[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	2 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	1 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	9048 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	4 ms	9816 KB	Time limit exceeded (wall clock)
13	Execution timed out	5 ms	9304 KB	Time limit exceeded (wall clock)
14	Execution timed out	7 ms	9816 KB	Time limit exceeded (wall clock)
15	Execution timed out	9 ms	12116 KB	Time limit exceeded (wall clock)

Subtask #2

0 / 85.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	12 ms	12120 KB	Time limit exceeded (wall clock)
2	Execution timed out	12 ms	11096 KB	Time limit exceeded (wall clock)
3	Execution timed out	15 ms	13912 KB	Time limit exceeded (wall clock)
4	Execution timed out	6 ms	9816 KB	Time limit exceeded (wall clock)
5	Execution timed out	6 ms	11352 KB	Time limit exceeded (wall clock)
6	Execution timed out	9 ms	10584 KB	Time limit exceeded (wall clock)
7	Execution timed out	18 ms	11244 KB	Time limit exceeded (wall clock)
8	Execution timed out	27 ms	15800 KB	Time limit exceeded (wall clock)
9	Execution timed out	26 ms	15208 KB	Time limit exceeded (wall clock)
10	Execution timed out	29 ms	19540 KB	Time limit exceeded (wall clock)
11	Execution timed out	34 ms	13996 KB	Time limit exceeded (wall clock)
12	Execution timed out	53 ms	16208 KB	Time limit exceeded (wall clock)
13	Execution timed out	32 ms	16464 KB	Time limit exceeded (wall clock)
14	Execution timed out	44 ms	15696 KB	Time limit exceeded (wall clock)
15	Execution timed out	32 ms	19800 KB	Time limit exceeded (wall clock)
16	Execution timed out	36 ms	25348 KB	Time limit exceeded (wall clock)
17	Execution timed out	41 ms	24148 KB	Time limit exceeded (wall clock)