oj.uz

Submission #988431

# Submission time Handle Problem Language Result Execution time Memory
988431 2024-05-24T17:08:25 Z orcslop Regions (IOI09_regions) C++17
35 / 100
 2727 ms 67816 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long; 
#define pb push_back
#define all(x) begin(x), end(x)
#define sz(x) (int) (x).size()
#define f first
#define s second
#define mkp make_pair
#define pii pair<int, int>

const int MAXR = 25005; 
const int MAXN = 2e5 + 5; 
const int RT = 450; 

int n, r, q, timer; 
int h[MAXN]; 
int tin[MAXN]; 
int subs[MAXN]; 
int pre[RT][MAXN]; 
int tree[2 * MAXN]; 
map<int, int> mp; 
vector<int> adj[MAXN]; 
vector<int> eul[MAXR], occ[MAXR]; 

void dfs(int node, int prev){
    subs[node] = 1; 
    tin[node] = timer++; 
    for(auto x : adj[node]){
        if(x == prev) continue; 
        dfs(x, node); 
        subs[node] += subs[x]; 
    }
}

int query(int a, int b){
    a += n; 
    b += n; 
    int s = 0; 
    while(a <= b){
        if(a % 2 == 1) s += tree[a++]; 
        if(b % 2 == 0) s += tree[b--]; 
        a /= 2; b /= 2; 
    }
    return s; 
}

int32_t main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> r >> q; 
    cin >> h[0]; 
    occ[h[0]].pb(0); 
    for(int i = 1; i < n; i++){
        int x; 
        cin >> x >> h[i]; 
        adj[--x].pb(i); 
        adj[i].pb(x); 
        occ[h[i]].pb(i); 
    }
    dfs(0, -1); 
    for(int i = 1; i < MAXR; i++){
        for(auto x : occ[i]) eul[i].pb(tin[x]); 
        sort(all(eul[i])); 
        sort(all(occ[i]), [](int &a, int &b){
            return tin[a] < tin[b]; 
        }); 
        if(occ[i].size() >= RT) {
            int index = 0; 
            for(int j = 0; j < n; j++){
                if(j == occ[i][index]){
                    tree[j + n] = 1; 
                    index++; 
                }
                else tree[j + n] = 0; 
            }
            for(int j = n - 1; j >= 0; j--){
                tree[j] = tree[2 * j] + tree[2 * j + 1]; 
            }
            for(int j = 1; j < MAXN; j++){
                for(auto x : occ[j]){
                    pre[mp.size()][j] += query(tin[x], tin[x] + subs[x] - 1); 
                }
            }
            mp[i] = mp.size(); 
        }
    }
    for(int i = 0; i < q; i++){
        int a, b; 
        cin >> a >> b; 
        if(occ[a].size() >= RT) cout << pre[mp[a]][b] << endl; 
        else{
            int ans = 0; 
            for(auto x : occ[a]){
                // cout << tin[x] << ' ' << tin[x] + subs[x] - 1 << endl; 
                auto lb = lower_bound(all(eul[b]), tin[x]); 
                auto ub = upper_bound(all(eul[b]), tin[x] + subs[x] - 1); 
                ans += ub - lb; 
            }
            // cout << "______\n"; 
            cout << ans << endl; 
        }
    }
    // cout << tin[0] << endl; 
    return 0; 
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6744 KB Output is correct
2 Correct 3 ms 6744 KB Output is correct
3 Correct 4 ms 6744 KB Output is correct
4 Correct 5 ms 6744 KB Output is correct
5 Correct 7 ms 6744 KB Output is correct
6 Correct 16 ms 6744 KB Output is correct
7 Correct 20 ms 6744 KB Output is correct
8 Correct 16 ms 6744 KB Output is correct
9 Correct 33 ms 7256 KB Output is correct
10 Correct 43 ms 7252 KB Output is correct
11 Correct 67 ms 7644 KB Output is correct
12 Correct 86 ms 8024 KB Output is correct
13 Correct 107 ms 8024 KB Output is correct
14 Correct 168 ms 8508 KB Output is correct
15 Correct 205 ms 12140 KB Output is correct

Subtask #2
20.0 / 85.0

# Verdict Execution time Memory Grader output
1 Runtime error 45 ms 23680 KB Execution killed with signal 11
2 Runtime error 42 ms 22608 KB Execution killed with signal 11
3 Runtime error 50 ms 28264 KB Execution killed with signal 11
4 Correct 160 ms 8536 KB Output is correct
5 Correct 179 ms 10688 KB Output is correct
6 Runtime error 37 ms 19520 KB Execution killed with signal 11
7 Runtime error 40 ms 21672 KB Execution killed with signal 11
8 Runtime error 63 ms 35228 KB Execution killed with signal 11
9 Correct 1530 ms 16976 KB Output is correct
10 Runtime error 108 ms 47492 KB Execution killed with signal 11
11 Correct 2727 ms 19128 KB Output is correct
12 Runtime error 128 ms 35676 KB Execution killed with signal 11
13 Runtime error 110 ms 38144 KB Execution killed with signal 11
14 Runtime error 142 ms 37360 KB Execution killed with signal 11
15 Runtime error 132 ms 49176 KB Execution killed with signal 11
16 Runtime error 145 ms 67816 KB Execution killed with signal 11
17 Runtime error 130 ms 62320 KB Execution killed with signal 11