oj.uz

Submission #988448

# Submission time Handle Problem Language Result Execution time Memory
988448 2024-05-24T17:41:21 Z orcslop Regions (IOI09_regions) C++17
35 / 100
 3994 ms 34292 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 < eul[i].size() && j == eul[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 < MAXR; 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]){
                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 << ans << 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 < eul[i].size() && j == eul[i][index]){
      |                    ~~~~~~^~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6744 KB Output is correct
2 Correct 4 ms 6232 KB Output is correct
3 Correct 5 ms 6232 KB Output is correct
4 Correct 5 ms 6232 KB Output is correct
5 Correct 8 ms 6232 KB Output is correct
6 Correct 11 ms 6232 KB Output is correct
7 Correct 13 ms 6744 KB Output is correct
8 Correct 19 ms 6744 KB Output is correct
9 Correct 32 ms 7000 KB Output is correct
10 Correct 44 ms 7256 KB Output is correct
11 Correct 64 ms 7644 KB Output is correct
12 Correct 88 ms 7740 KB Output is correct
13 Correct 102 ms 7544 KB Output is correct
14 Correct 163 ms 8492 KB Output is correct
15 Correct 184 ms 12136 KB Output is correct

Subtask #2
20.0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 1409 ms 12204 KB Output isn't correct
2 Incorrect 1545 ms 11568 KB Output isn't correct
3 Incorrect 2117 ms 14580 KB Output isn't correct
4 Correct 173 ms 8536 KB Output is correct
5 Correct 224 ms 10840 KB Output is correct
6 Incorrect 532 ms 14048 KB Output isn't correct
7 Incorrect 1147 ms 11812 KB Output isn't correct
8 Incorrect 1778 ms 22516 KB Output isn't correct
9 Correct 1591 ms 17268 KB Output is correct
10 Incorrect 3994 ms 30412 KB Output isn't correct
11 Correct 2653 ms 19016 KB Output is correct
12 Incorrect 903 ms 18860 KB Output isn't correct
13 Incorrect 1336 ms 19940 KB Output isn't correct
14 Incorrect 1815 ms 21716 KB Output isn't correct
15 Incorrect 2330 ms 25276 KB Output isn't correct
16 Incorrect 2269 ms 34292 KB Output isn't correct
17 Incorrect 2677 ms 34068 KB Output isn't correct