oj.uz

Submission #998285

# Submission time Handle Problem Language Result Execution time Memory
998285 2024-06-13T13:52:14 Z BF001 Regions (IOI09_regions) C++17
0 / 100
 101 ms 30168 KB 
#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];
vector<vector<int>> gt;

void init(int u, int p){
	tin[u] = ++tim;
	rg[h[u]].push_back(tin[u]);
	node[tim] = u;
	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[i]]) continue;
    	vs[h[i]] = 1;
    	if (rg[h[i]].size() <= blsiz) continue;
    	vector<int> pre(n + 2, 0);
    	for (auto x : rg[h[i]]){
    		int l = tin[node[x]], r = tout[node[x]];
    		pre[l]++; pre[r + 1]--;
    	}
    	gt.push_back(vector<int> (r + 1));
    	idx[h[i]] = ++cnt;
    	for (int j = 1; j <= n; j++){
    		pre[j] += pre[j - 1];
    		gt[idx[h[i]]][h[node[j]]] += pre[j];  
    	}
    }

    while (q--){
    	int r1, r2;
    	cin >> r1 >> r2;
    	if (rg[r1].size() > blsiz){
    		cout << gt[idx[r1]][r2] << "\n";
    	}
    	else {
    		int res = 0;
    		for (auto x : rg[r1]){
    			int l = tin[node[x]], r = tout[node[x]];
    			res += find(r2, r) - find(r2, l);
    		}
    		cout << res << "\n";
    	}
    }

    return 0;
}

Compilation message

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

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2 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 1 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 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 9560 KB Time limit exceeded (wall clock)
13 Execution timed out 7 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 11 ms 12376 KB Time limit exceeded (wall clock)

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 24 ms 12376 KB Time limit exceeded (wall clock)
2 Execution timed out 17 ms 11292 KB Time limit exceeded (wall clock)
3 Execution timed out 18 ms 14072 KB Time limit exceeded (wall clock)
4 Execution timed out 6 ms 9816 KB Time limit exceeded (wall clock)
5 Execution timed out 10 ms 11352 KB Time limit exceeded (wall clock)
6 Execution timed out 22 ms 12424 KB Time limit exceeded (wall clock)
7 Execution timed out 29 ms 13636 KB Time limit exceeded (wall clock)
8 Execution timed out 57 ms 20120 KB Time limit exceeded (wall clock)
9 Execution timed out 30 ms 15192 KB Time limit exceeded (wall clock)
10 Execution timed out 101 ms 30168 KB Time limit exceeded (wall clock)
11 Execution timed out 56 ms 14416 KB Time limit exceeded (wall clock)
12 Execution timed out 50 ms 17128 KB Time limit exceeded (wall clock)
13 Execution timed out 40 ms 17256 KB Time limit exceeded (wall clock)
14 Execution timed out 58 ms 18324 KB Time limit exceeded (wall clock)
15 Execution timed out 41 ms 21056 KB Time limit exceeded (wall clock)
16 Execution timed out 40 ms 26444 KB Time limit exceeded (wall clock)
17 Execution timed out 62 ms 26944 KB Time limit exceeded (wall clock)