oj.uz

Submission #998291

# Submission time Handle Problem Language Result Execution time Memory
998291 2024-06-13T14:10:17 Z BF001 Regions (IOI09_regions) C++17
0 / 100
 1380 ms 25360 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];
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(){
      
    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:50:32: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'const int' [-Wsign-compare]
   50 |      if (rg[h[node[i]]].size() <= blsiz) continue;
      |          ~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 8792 KB Output isn't correct
2 Incorrect 2 ms 8792 KB Output isn't correct
3 Incorrect 3 ms 8792 KB Output isn't correct
4 Incorrect 4 ms 8792 KB Output isn't correct
5 Incorrect 4 ms 8792 KB Output isn't correct
6 Incorrect 14 ms 8792 KB Output isn't correct
7 Incorrect 15 ms 8792 KB Output isn't correct
8 Incorrect 16 ms 8792 KB Output isn't correct
9 Incorrect 27 ms 9048 KB Output isn't correct
10 Incorrect 38 ms 9048 KB Output isn't correct
11 Incorrect 65 ms 9304 KB Output isn't correct
12 Incorrect 66 ms 9816 KB Output isn't correct
13 Incorrect 95 ms 9304 KB Output isn't correct
14 Incorrect 78 ms 9724 KB Output isn't correct
15 Incorrect 99 ms 12120 KB Output isn't correct

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 549 ms 12112 KB Output isn't correct
2 Incorrect 643 ms 10832 KB Output isn't correct
3 Incorrect 852 ms 13904 KB Output isn't correct
4 Incorrect 148 ms 9816 KB Output isn't correct
5 Incorrect 202 ms 11352 KB Output isn't correct
6 Incorrect 394 ms 10584 KB Output isn't correct
7 Incorrect 591 ms 11344 KB Output isn't correct
8 Incorrect 601 ms 15856 KB Output isn't correct
9 Incorrect 895 ms 14928 KB Output isn't correct
10 Incorrect 1145 ms 19600 KB Output isn't correct
11 Incorrect 1317 ms 13928 KB Output isn't correct
12 Incorrect 609 ms 16212 KB Output isn't correct
13 Incorrect 819 ms 16344 KB Output isn't correct
14 Incorrect 1010 ms 15860 KB Output isn't correct
15 Incorrect 1244 ms 19788 KB Output isn't correct
16 Incorrect 1380 ms 25360 KB Output isn't correct
17 Incorrect 1328 ms 24144 KB Output isn't correct