oj.uz

Submission #988430

# Submission time Handle Problem Language Result Execution time Memory
988430 2024-05-24T17:06:45 Z orcslop Regions (IOI09_regions) C++17
35 / 100
 2684 ms 67620 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; 
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 4 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 6 ms 6744 KB Output is correct
6 Correct 11 ms 6744 KB Output is correct
7 Correct 16 ms 6744 KB Output is correct
8 Correct 16 ms 6744 KB Output is correct
9 Correct 25 ms 7256 KB Output is correct
10 Correct 42 ms 7256 KB Output is correct
11 Correct 75 ms 7644 KB Output is correct
12 Correct 87 ms 8024 KB Output is correct
13 Correct 93 ms 8024 KB Output is correct
14 Correct 146 ms 8280 KB Output is correct
15 Correct 198 ms 12132 KB Output is correct

Subtask #2
20.0 / 85.0

# Verdict Execution time Memory Grader output
1 Runtime error 41 ms 23248 KB Execution killed with signal 11
2 Runtime error 39 ms 22016 KB Execution killed with signal 11
3 Runtime error 49 ms 28136 KB Execution killed with signal 11
4 Correct 166 ms 8524 KB Output is correct
5 Correct 290 ms 11092 KB Output is correct
6 Runtime error 40 ms 19564 KB Execution killed with signal 11
7 Runtime error 48 ms 21720 KB Execution killed with signal 11
8 Runtime error 70 ms 35156 KB Execution killed with signal 11
9 Correct 1609 ms 17080 KB Output is correct
10 Runtime error 117 ms 47512 KB Execution killed with signal 11
11 Correct 2684 ms 18908 KB Output is correct
12 Runtime error 113 ms 35688 KB Execution killed with signal 11
13 Runtime error 96 ms 38112 KB Execution killed with signal 11
14 Runtime error 112 ms 37672 KB Execution killed with signal 11
15 Runtime error 140 ms 49120 KB Execution killed with signal 11
16 Runtime error 158 ms 67620 KB Execution killed with signal 11
17 Runtime error 124 ms 62428 KB Execution killed with signal 11