oj.uz

Submission #1064660

# Submission time Handle Problem Language Result Execution time Memory
1064660 2024-08-18T16:32:43 Z orcslop Regions (IOI09_regions) C++17
35 / 100
 2624 ms 35560 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; 
}

Compilation message

regions.cpp: In function 'int32_t main()':
regions.cpp:89:17: warning: unused variable 'curr' [-Wunused-variable]
   89 |             int curr = mp[i] = mp.size();
      |                 ^~~~

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 10328 KB Output is correct
4 Correct 4 ms 10328 KB Output is correct
5 Correct 6 ms 10584 KB Output is correct
6 Correct 10 ms 10532 KB Output is correct
7 Correct 15 ms 10328 KB Output is correct
8 Correct 14 ms 10328 KB Output is correct
9 Correct 23 ms 10840 KB Output is correct
10 Correct 40 ms 10900 KB Output is correct
11 Correct 64 ms 11344 KB Output is correct
12 Correct 85 ms 11704 KB Output is correct
13 Correct 96 ms 11608 KB Output is correct
14 Correct 146 ms 11896 KB Output is correct
15 Correct 199 ms 15452 KB Output is correct

Subtask #2
20.0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 1361 ms 15024 KB Output isn't correct
2 Incorrect 1553 ms 14324 KB Output isn't correct
3 Incorrect 2100 ms 17196 KB Output isn't correct
4 Correct 167 ms 12120 KB Output is correct
5 Correct 257 ms 14176 KB Output is correct
6 Incorrect 365 ms 13480 KB Output isn't correct
7 Incorrect 1012 ms 14352 KB Output isn't correct
8 Incorrect 640 ms 20892 KB Output isn't correct
9 Correct 1633 ms 19824 KB Output is correct
10 Incorrect 2482 ms 26624 KB Output isn't correct
11 Correct 2624 ms 21488 KB Output is correct
12 Incorrect 922 ms 20124 KB Output isn't correct
13 Incorrect 1358 ms 21372 KB Output isn't correct
14 Incorrect 1601 ms 21272 KB Output isn't correct
15 Incorrect 2391 ms 26380 KB Output isn't correct
16 Incorrect 2290 ms 35560 KB Output isn't correct
17 Incorrect 2190 ms 33356 KB Output isn't correct