| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 998178 |
2024-06-13T11:30:38 Z |
BF001 |
Regions (IOI09_regions) |
C++17 |
|
195 ms |
34100 KB |
#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);
}
return 0;
while (q--){
int r1, r2;
cin >> r1 >> r2;
if (rg[r1].size() >= blsiz){
cout << gt[idx[r1]][r2] << "\n";
continue;
}
int res = 0;
for (auto x : v[r1]){
res += find(r2, tout[x]) - find(r2, tin[x] - 1);
}
cout << res << "\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;
| ~~~~~~~~~~~~~^~~~~~~
regions.cpp:70:21: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
70 | if (rg[r1].size() >= blsiz){
| ~~~~~~~~~~~~~~^~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
8792 KB |
Unexpected end of file - int32 expected |
| 2 |
Incorrect |
1 ms |
8792 KB |
Unexpected end of file - int32 expected |
| 3 |
Incorrect |
1 ms |
8792 KB |
Unexpected end of file - int32 expected |
| 4 |
Incorrect |
1 ms |
8792 KB |
Unexpected end of file - int32 expected |
| 5 |
Incorrect |
1 ms |
8792 KB |
Unexpected end of file - int32 expected |
| 6 |
Incorrect |
1 ms |
8792 KB |
Unexpected end of file - int32 expected |
| 7 |
Incorrect |
2 ms |
8792 KB |
Unexpected end of file - int32 expected |
| 8 |
Incorrect |
2 ms |
8792 KB |
Unexpected end of file - int32 expected |
| 9 |
Incorrect |
3 ms |
9048 KB |
Unexpected end of file - int32 expected |
| 10 |
Incorrect |
3 ms |
9048 KB |
Unexpected end of file - int32 expected |
| 11 |
Incorrect |
5 ms |
9300 KB |
Unexpected end of file - int32 expected |
| 12 |
Incorrect |
5 ms |
9816 KB |
Unexpected end of file - int32 expected |
| 13 |
Incorrect |
5 ms |
9332 KB |
Unexpected end of file - int32 expected |
| 14 |
Incorrect |
9 ms |
10048 KB |
Unexpected end of file - int32 expected |
| 15 |
Incorrect |
9 ms |
13656 KB |
Unexpected end of file - int32 expected |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
50 ms |
13204 KB |
Unexpected end of file - int32 expected |
| 2 |
Incorrect |
44 ms |
11600 KB |
Unexpected end of file - int32 expected |
| 3 |
Incorrect |
35 ms |
15448 KB |
Unexpected end of file - int32 expected |
| 4 |
Incorrect |
7 ms |
10072 KB |
Unexpected end of file - int32 expected |
| 5 |
Incorrect |
8 ms |
11608 KB |
Unexpected end of file - int32 expected |
| 6 |
Incorrect |
76 ms |
12844 KB |
Unexpected end of file - int32 expected |
| 7 |
Incorrect |
91 ms |
14208 KB |
Unexpected end of file - int32 expected |
| 8 |
Incorrect |
102 ms |
22860 KB |
Unexpected end of file - int32 expected |
| 9 |
Incorrect |
32 ms |
16728 KB |
Unexpected end of file - int32 expected |
| 10 |
Incorrect |
195 ms |
34100 KB |
Unexpected end of file - int32 expected |
| 11 |
Incorrect |
42 ms |
16208 KB |
Unexpected end of file - int32 expected |
| 12 |
Incorrect |
68 ms |
17820 KB |
Unexpected end of file - int32 expected |
| 13 |
Incorrect |
60 ms |
18512 KB |
Unexpected end of file - int32 expected |
| 14 |
Incorrect |
171 ms |
19536 KB |
Unexpected end of file - int32 expected |
| 15 |
Incorrect |
47 ms |
24400 KB |
Unexpected end of file - int32 expected |
| 16 |
Incorrect |
56 ms |
33540 KB |
Unexpected end of file - int32 expected |
| 17 |
Incorrect |
96 ms |
33036 KB |
Unexpected end of file - int32 expected |
