| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 998177 |
2024-06-13T11:30:04 Z |
BF001 |
Regions (IOI09_regions) |
C++17 |
|
74 ms |
27192 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);
return 0;
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);
}
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:60:20: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
60 | if (rg[i].size() < blsiz) continue;
| ~~~~~~~~~~~~~^~~~~~~
regions.cpp:69:21: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
69 | if (rg[r1].size() >= blsiz){
| ~~~~~~~~~~~~~~^~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
8792 KB |
Unexpected end of file - int32 expected |
| 2 |
Incorrect |
2 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 |
2 ms |
8792 KB |
Unexpected end of file - int32 expected |
| 6 |
Incorrect |
2 ms |
6232 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 |
2 ms |
9048 KB |
Unexpected end of file - int32 expected |
| 10 |
Incorrect |
3 ms |
9048 KB |
Unexpected end of file - int32 expected |
| 11 |
Incorrect |
6 ms |
9304 KB |
Unexpected end of file - int32 expected |
| 12 |
Incorrect |
7 ms |
9904 KB |
Unexpected end of file - int32 expected |
| 13 |
Incorrect |
6 ms |
9560 KB |
Unexpected end of file - int32 expected |
| 14 |
Incorrect |
8 ms |
10036 KB |
Unexpected end of file - int32 expected |
| 15 |
Incorrect |
12 ms |
12508 KB |
Unexpected end of file - int32 expected |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
21 ms |
12508 KB |
Unexpected end of file - int32 expected |
| 2 |
Incorrect |
18 ms |
11328 KB |
Unexpected end of file - int32 expected |
| 3 |
Incorrect |
19 ms |
14424 KB |
Unexpected end of file - int32 expected |
| 4 |
Incorrect |
9 ms |
10044 KB |
Unexpected end of file - int32 expected |
| 5 |
Incorrect |
13 ms |
11608 KB |
Unexpected end of file - int32 expected |
| 6 |
Incorrect |
14 ms |
10968 KB |
Unexpected end of file - int32 expected |
| 7 |
Incorrect |
18 ms |
11908 KB |
Unexpected end of file - int32 expected |
| 8 |
Incorrect |
27 ms |
16720 KB |
Unexpected end of file - int32 expected |
| 9 |
Incorrect |
37 ms |
16860 KB |
Unexpected end of file - int32 expected |
| 10 |
Incorrect |
47 ms |
21540 KB |
Unexpected end of file - int32 expected |
| 11 |
Incorrect |
53 ms |
16256 KB |
Unexpected end of file - int32 expected |
| 12 |
Incorrect |
68 ms |
17704 KB |
Unexpected end of file - int32 expected |
| 13 |
Incorrect |
62 ms |
17980 KB |
Unexpected end of file - int32 expected |
| 14 |
Incorrect |
74 ms |
17592 KB |
Unexpected end of file - int32 expected |
| 15 |
Incorrect |
46 ms |
21984 KB |
Unexpected end of file - int32 expected |
| 16 |
Incorrect |
42 ms |
27192 KB |
Unexpected end of file - int32 expected |
| 17 |
Incorrect |
40 ms |
26184 KB |
Unexpected end of file - int32 expected |
