oj.uz

Submission #988429

# Submission time Handle Problem Language Result Execution time Memory
988429 2024-05-24T17:00:02 Z orcslop Regions (IOI09_regions) C++17
0 / 100
 150 ms 70252 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] << '\n'; 
        else{
            int ans = 0; 
            for(auto x : occ[a]){
                // cout << tin[x] << ' ' << tin[x] + subs[x] - 1 << '\n'; 
                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 << '\n'; 
        }
    }
    // cout << tin[0] << '\n'; 
    return 0; 
}

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4 ms 8792 KB Time limit exceeded (wall clock)
2 Execution timed out 3 ms 6744 KB Time limit exceeded (wall clock)
3 Execution timed out 2 ms 6744 KB Time limit exceeded (wall clock)
4 Execution timed out 2 ms 6744 KB Time limit exceeded (wall clock)
5 Execution timed out 2 ms 6744 KB Time limit exceeded (wall clock)
6 Execution timed out 4 ms 6748 KB Time limit exceeded (wall clock)
7 Execution timed out 2 ms 6744 KB Time limit exceeded (wall clock)
8 Execution timed out 6 ms 8792 KB Time limit exceeded (wall clock)
9 Execution timed out 4 ms 9304 KB Time limit exceeded (wall clock)
10 Execution timed out 6 ms 7256 KB Time limit exceeded (wall clock)
11 Execution timed out 7 ms 7576 KB Time limit exceeded (wall clock)
12 Execution timed out 10 ms 8536 KB Time limit exceeded (wall clock)
13 Execution timed out 11 ms 9812 KB Time limit exceeded (wall clock)
14 Execution timed out 10 ms 10488 KB Time limit exceeded (wall clock)
15 Execution timed out 15 ms 13748 KB Time limit exceeded (wall clock)

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Runtime error 47 ms 26092 KB Execution killed with signal 11
2 Runtime error 45 ms 24732 KB Execution killed with signal 11
3 Runtime error 60 ms 34384 KB Execution killed with signal 11
4 Execution timed out 11 ms 10328 KB Time limit exceeded (wall clock)
5 Execution timed out 14 ms 10840 KB Time limit exceeded (wall clock)
6 Runtime error 33 ms 19600 KB Execution killed with signal 11
7 Runtime error 44 ms 21564 KB Execution killed with signal 11
8 Runtime error 69 ms 35220 KB Execution killed with signal 11
9 Execution timed out 76 ms 17116 KB Time limit exceeded (wall clock)
10 Runtime error 104 ms 48768 KB Execution killed with signal 11
11 Execution timed out 83 ms 19216 KB Time limit exceeded (wall clock)
12 Runtime error 129 ms 36504 KB Execution killed with signal 11
13 Runtime error 124 ms 41108 KB Execution killed with signal 11
14 Runtime error 119 ms 40028 KB Execution killed with signal 11
15 Runtime error 150 ms 51656 KB Execution killed with signal 11
16 Runtime error 137 ms 70252 KB Execution killed with signal 11
17 Runtime error 138 ms 63024 KB Execution killed with signal 11