oj.uz

Submission #793499

# Submission time Handle Problem Language Result Execution time Memory
793499 2023-07-25T22:59:47 Z phoebe Regions (IOI09_regions) C++17
100 / 100
 4872 ms 79304 KB 
#include <bits/stdc++.h>
using namespace std;
 
#pragma GCC optimize("03")
 
// #define int long long
#define ll long long
#define pii pair<int, int>
#define F first
#define S second
#define PB push_back
#define ALL(x) x.begin(), x.end()
#define FOR(i, n) for (int i = 0; i < n; i++)
#define NYOOM ios::sync_with_stdio(0); cin.tie(0);
// #define endl '\n'
const int INF = 1e9 + 7;
const ll LLINF = 1ll<<60;
 
const int maxn = 2e5 + 10, block = 400, maxr = 25005;
int n, r, q, h[maxn], arrive[maxn], leave[maxn], 
cnt[maxn / block][maxr] = {0}, // cnt[i][j] = # region i as manager of j
timer = 0, cur[block] = {0}, get_idx[maxn], idx = 0;
vector<int> adj[maxn], bruh[maxr], // bruh[i] = vector of arrive time of region i
region[maxr]; // region[i] = vector of all nodes in region i
 
void dfs(int v){ // O(n sqrt n)
    arrive[v] = timer++;
    bruh[h[v]].PB(arrive[v]);
    FOR(i, maxn / block) cnt[i][h[v]] += cur[i];
    if (get_idx[h[v]] != -1) cur[get_idx[h[v]]]++;
    for (auto u : adj[v]){
        dfs(u);
    }
    if (get_idx[h[v]] != -1) cur[get_idx[h[v]]]--;
    leave[v] = timer++;
}
 
signed main(){
    NYOOM;
    fill(get_idx, get_idx + maxn, -1);
    cin >> n >> r >> q;
    cin >> h[1]; region[h[1]].PB(1);
    for (int i = 2; i <= n; i++){
        int s; cin >> s >> h[i];
        adj[s].PB(i); region[h[i]].PB(i);
    }
    for (int i = 1; i <= r; i++){
        if (region[i].size() >= block) get_idx[i] = idx++;
    }
    dfs(1);
    FOR(i, q){
        int r1, r2; cin >> r1 >> r2;
        if (get_idx[r1] != -1){
            cout << cnt[get_idx[r1]][r2] << endl;
            continue;
        }
        int re = 0;
        for (auto v : region[r1]){ // o(sqrt n log n)
            int l = lower_bound(ALL(bruh[r2]), arrive[v]) - bruh[r2].begin();
            int r = lower_bound(ALL(bruh[r2]), leave[v]) - bruh[r2].begin();
            // cout << l << ' ' << r << endl; 
            re += r - l;
        }
        cout << re << endl;
    }
    // total = o(n sqrt n + q sqrt n log n)
}

Compilation message

regions.cpp: In function 'void dfs(int)':
regions.cpp:29:47: warning: iteration 400 invokes undefined behavior [-Waggressive-loop-optimizations]
   29 |     FOR(i, maxn / block) cnt[i][h[v]] += cur[i];
      |                                          ~~~~~^
regions.cpp:13:37: note: within this loop
   13 | #define FOR(i, n) for (int i = 0; i < n; i++)
......
   29 |     FOR(i, maxn / block) cnt[i][h[v]] += cur[i];
      |         ~~~~~~~~~~~~~~~              
regions.cpp:29:5: note: in expansion of macro 'FOR'
   29 |     FOR(i, maxn / block) cnt[i][h[v]] += cur[i];
      |     ^~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9040 KB Output is correct
2 Correct 4 ms 9040 KB Output is correct
3 Correct 5 ms 9040 KB Output is correct
4 Correct 5 ms 9044 KB Output is correct
5 Correct 15 ms 9184 KB Output is correct
6 Correct 21 ms 9552 KB Output is correct
7 Correct 31 ms 9424 KB Output is correct
8 Correct 19 ms 9552 KB Output is correct
9 Correct 28 ms 10320 KB Output is correct
10 Correct 83 ms 10448 KB Output is correct
11 Correct 102 ms 10444 KB Output is correct
12 Correct 143 ms 11368 KB Output is correct
13 Correct 201 ms 10724 KB Output is correct
14 Correct 245 ms 11084 KB Output is correct
15 Correct 254 ms 14312 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1708 ms 14324 KB Output is correct
2 Correct 2068 ms 13012 KB Output is correct
3 Correct 2500 ms 16568 KB Output is correct
4 Correct 313 ms 18492 KB Output is correct
5 Correct 458 ms 22416 KB Output is correct
6 Correct 671 ms 25672 KB Output is correct
7 Correct 1403 ms 32632 KB Output is correct
8 Correct 1296 ms 38628 KB Output is correct
9 Correct 2792 ms 48200 KB Output is correct
10 Correct 2876 ms 71584 KB Output is correct
11 Correct 4872 ms 65248 KB Output is correct
12 Correct 2021 ms 51044 KB Output is correct
13 Correct 2185 ms 51476 KB Output is correct
14 Correct 2747 ms 58972 KB Output is correct
15 Correct 3517 ms 72096 KB Output is correct
16 Correct 3422 ms 79304 KB Output is correct
17 Correct 3159 ms 69904 KB Output is correct