oj.uz

답안 #998288

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
998288 2024-06-13T14:07:39 Z BF001 Regions (IOI09_regions) C++17
0 / 100
 53 ms 25348 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(){
    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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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)