oj.uz

Submission #1064653

# Submission time Handle Problem Language Result Execution time Memory
1064653 2024-08-18T16:26:25 Z orcslop Regions (IOI09_regions) C++17
40 / 100
 8000 ms 35664 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; 

template <class T> class BIT {
  private:
    int n;
    vector<T> bit;
    vector<T> arr;

  public:
    BIT(int n) : n(n), bit(n + 1), arr(n) {}

    void set(int k, T val) { add(k, val - arr[k]); }

    void add(int k, T val) {
        arr[k] += val;
        k++;
        for (; k <= n; k += k & -k) { bit[k] += val; }
    }

    T query(int a, int b) {
        b++;
        T s = 0;
        for (; a > 0; a -= a & -a) { s -= bit[a]; }
        for (; b > 0; b -= b & -b) { s += bit[b]; }
        return s;
    }
};
 
int n, r, q, timer; 
int h[MAXN]; 
int tin[MAXN]; 
int subs[MAXN]; 
int pre[RT][MAXN]; 
BIT<int> bit(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]; 
    }
}
 
int32_t main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> r >> q; 
    // int RT = sqrt(n); 
    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 = 0; i < n; i++){
    //     cout << tin[i] << ' '; 
    // }
    // cout << '\n'; 
    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]; 
        }); 
    }
    for(int i = 1; i < MAXR; i++){
        if(occ[i].size() >= RT) {
            int curr = mp[i] = mp.size(); 
            for(int j = 1; j < MAXR; j++){
                for(auto x : eul[j]) {
                    bit.add(x, 1); 
                }
                // for(int i = 0; i < n; i++){
                //     cout << bit.query(k, k) << ' '; 
                // }
                // cout << '\n'; 
                for(auto x : occ[i]){
                    pre[curr][j] += bit.query(tin[x], tin[x] + subs[x] - 1); 
                }
                for(auto x : eul[j]){
                    bit.add(x, -1); 
                }
            }
        }
    }
    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; 
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10328 KB Output is correct
2 Correct 2 ms 10328 KB Output is correct
3 Correct 3 ms 10428 KB Output is correct
4 Correct 4 ms 10328 KB Output is correct
5 Correct 7 ms 10328 KB Output is correct
6 Correct 11 ms 10532 KB Output is correct
7 Correct 21 ms 10576 KB Output is correct
8 Correct 18 ms 10544 KB Output is correct
9 Correct 32 ms 11040 KB Output is correct
10 Correct 55 ms 10896 KB Output is correct
11 Correct 81 ms 11292 KB Output is correct
12 Correct 102 ms 11700 KB Output is correct
13 Correct 105 ms 11608 KB Output is correct
14 Correct 158 ms 11896 KB Output is correct
15 Correct 176 ms 15444 KB Output is correct

Subtask #2
25.0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8052 ms 16044 KB Time limit exceeded
2 Execution timed out 8007 ms 14672 KB Time limit exceeded
3 Execution timed out 8038 ms 17428 KB Time limit exceeded
4 Correct 194 ms 12120 KB Output is correct
5 Correct 247 ms 14180 KB Output is correct
6 Execution timed out 8045 ms 18916 KB Time limit exceeded
7 Correct 3076 ms 15668 KB Output is correct
8 Execution timed out 8032 ms 25928 KB Time limit exceeded
9 Correct 1552 ms 19828 KB Output is correct
10 Execution timed out 8058 ms 30792 KB Time limit exceeded
11 Correct 2480 ms 21492 KB Output is correct
12 Execution timed out 8053 ms 20052 KB Time limit exceeded
13 Execution timed out 8053 ms 21328 KB Time limit exceeded
14 Execution timed out 8032 ms 21380 KB Time limit exceeded
15 Execution timed out 8018 ms 26192 KB Time limit exceeded
16 Execution timed out 8029 ms 35664 KB Time limit exceeded
17 Execution timed out 8045 ms 34128 KB Time limit exceeded