oj.uz

Submission #988438

# Submission time Handle Problem Language Result Execution time Memory
988438 2024-05-24T17:24:50 Z orcslop Regions (IOI09_regions) C++17
25 / 100
 3779 ms 34268 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 <= r; 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 <= r; j++){
                for(auto x : occ[j]){
                    //  cout << x << '\n';
                    // cout << tin[x]+subs[x]-1<<'\n';
                    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 4 ms 6232 KB Output is correct
2 Correct 4 ms 6232 KB Output is correct
3 Correct 5 ms 6232 KB Output is correct
4 Correct 7 ms 6232 KB Output is correct
5 Correct 7 ms 6232 KB Output is correct
6 Correct 13 ms 6232 KB Output is correct
7 Correct 16 ms 6232 KB Output is correct
8 Correct 18 ms 6488 KB Output is correct
9 Correct 24 ms 7000 KB Output is correct
10 Correct 47 ms 6908 KB Output is correct
11 Correct 62 ms 7192 KB Output is correct
12 Correct 80 ms 7768 KB Output is correct
13 Correct 98 ms 7512 KB Output is correct
14 Correct 175 ms 7888 KB Output is correct
15 Correct 209 ms 11688 KB Output is correct

Subtask #2
10.0 / 85.0

# Verdict Execution time Memory Grader output
1 Runtime error 1455 ms 12208 KB Execution killed with signal 13
2 Runtime error 1598 ms 11568 KB Execution killed with signal 13
3 Runtime error 2179 ms 14584 KB Execution killed with signal 13
4 Correct 153 ms 8216 KB Output is correct
5 Correct 216 ms 10268 KB Output is correct
6 Incorrect 510 ms 11996 KB Output isn't correct
7 Runtime error 1123 ms 11972 KB Execution killed with signal 13
8 Incorrect 1862 ms 22644 KB Output isn't correct
9 Runtime error 1524 ms 16700 KB Execution killed with signal 13
10 Runtime error 3779 ms 30468 KB Execution killed with signal 13
11 Runtime error 2855 ms 18552 KB Execution killed with signal 13
12 Runtime error 946 ms 18764 KB Execution killed with signal 13
13 Incorrect 1312 ms 19900 KB Output isn't correct
14 Incorrect 1991 ms 21720 KB Output isn't correct
15 Runtime error 2394 ms 25216 KB Execution killed with signal 13
16 Incorrect 2253 ms 34268 KB Output isn't correct
17 Runtime error 2643 ms 34136 KB Execution killed with signal 13