oj.uz

Submission #988433

# Submission time Handle Problem Language Result Execution time Memory
988433 2024-05-24T17:13:02 Z orcslop Regions (IOI09_regions) C++17
35 / 100
 2813 ms 67664 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(index < occ[i].size() && 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; 
}

Compilation message

regions.cpp: In function 'int32_t main()':
regions.cpp:70:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |                 if(index < occ[i].size() && j == occ[i][index]){
      |                    ~~~~~~^~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6744 KB Output is correct
2 Correct 4 ms 6744 KB Output is correct
3 Correct 4 ms 6744 KB Output is correct
4 Correct 6 ms 6744 KB Output is correct
5 Correct 7 ms 6744 KB Output is correct
6 Correct 10 ms 6744 KB Output is correct
7 Correct 17 ms 6744 KB Output is correct
8 Correct 21 ms 6744 KB Output is correct
9 Correct 24 ms 7256 KB Output is correct
10 Correct 43 ms 7256 KB Output is correct
11 Correct 68 ms 7512 KB Output is correct
12 Correct 87 ms 8024 KB Output is correct
13 Correct 104 ms 8024 KB Output is correct
14 Correct 161 ms 8560 KB Output is correct
15 Correct 195 ms 12144 KB Output is correct

Subtask #2
20.0 / 85.0

# Verdict Execution time Memory Grader output
1 Runtime error 43 ms 23288 KB Execution killed with signal 11
2 Runtime error 45 ms 22076 KB Execution killed with signal 11
3 Runtime error 52 ms 28116 KB Execution killed with signal 11
4 Correct 166 ms 8532 KB Output is correct
5 Correct 228 ms 10636 KB Output is correct
6 Runtime error 34 ms 19536 KB Execution killed with signal 11
7 Runtime error 58 ms 21676 KB Execution killed with signal 11
8 Runtime error 71 ms 35164 KB Execution killed with signal 11
9 Correct 1591 ms 17140 KB Output is correct
10 Runtime error 111 ms 47508 KB Execution killed with signal 11
11 Correct 2813 ms 19232 KB Output is correct
12 Runtime error 136 ms 35468 KB Execution killed with signal 11
13 Runtime error 110 ms 38496 KB Execution killed with signal 11
14 Runtime error 140 ms 37368 KB Execution killed with signal 11
15 Runtime error 149 ms 49368 KB Execution killed with signal 11
16 Runtime error 150 ms 67664 KB Execution killed with signal 11
17 Runtime error 133 ms 62424 KB Execution killed with signal 11