oj.uz

Submission #607124

# Submission time Handle Problem Language Result Execution time Memory
607124 2022-07-26T12:20:06 Z jhwest2 Regions (IOI09_regions) C++14
0 / 100
 8000 ms 71668 KB 
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 202020;
const int MAXR = 25252;
typedef long long ll;

int n, r, q, R[MAXN], P[MAXN], X[MAXN];
vector<int> G[MAXN];
vector<int> V[MAXR];
map<pair<int, int>, ll> M;


struct PST {
    vector<int> tree, l, r;

    int new_node() {
        tree.push_back(0);
        l.push_back(0);
        r.push_back(0);
        return (int)tree.size() - 1;
    }
    int init(int lo, int hi) {
        int idx = new_node();
        if (lo != hi) {
            int ll = init(lo, lo + hi >> 1);
            int rr = init(1 + (lo + hi >> 1), hi);
            l[idx] = ll;
            r[idx] = rr;
        }
        return idx;
    }
    int update(int s, int x, int lo, int hi, int p_idx) {
        int idx = new_node();
        if (lo == hi) {
            tree[idx] += x; return idx;
        }
        int mid = (lo + hi >> 1);
        int ll = (s <= mid) ? update(s, x, lo, mid, l[p_idx]) : l[p_idx];
        int rr = (s > mid) ? update(s, x, mid + 1, hi, r[p_idx]) : r[p_idx];
        l[idx] = ll;
        r[idx] = rr;
        tree[idx] = tree[ll] + tree[rr];
        return idx;
    }
    int get() { return tree.size(); }
    int query(int s, int lo, int hi, int idx) {
        if (lo == hi) return tree[idx];
        int mid = (lo + hi >> 1);
        if (s <= mid) return query(s, lo, mid, l[idx]);
        else return query(s, mid + 1, hi, r[idx]);
    }
} PST;

int p, LL[MAXN], RR[MAXN];
void dfs(int v) {
    LL[v] = ++p;
    for (int x : G[v]) dfs(x);
    RR[v] = p;
}
int main() {
    cin >> n >> r >> q;
    cin >> R[1]; V[R[1]].push_back(1);
    for (int i = 2; i <= n; i++) {
        cin >> P[i] >> R[i];
        G[P[i]].push_back(i);
        V[R[i]].push_back(i);
    }
    
    PST.init(1, r);
    for (int i = 1; i <= n; i++) {
        X[i] = PST.get();
        PST.update(R[i], 1, 1, r, X[P[i]]);
    }
    for (int i = 1; i <= r; i++) {
        sort(V[i].begin(), V[i].end());
    }
    dfs(1);

    while (q--) {
        int a, b; cin >> a >> b;
        if (M.find({ a, b }) != M.end()) {
            cout << M[{a, b}] << endl;
            continue;
        }
        ll ans = 0;
        if (V[a].size() < V[b].size()) {
            for (int x : V[a]) {
                ans += lower_bound(V[b].begin(), V[b].end(), RR[x]) -
                    lower_bound(V[b].begin(), V[b].end(), LL[x]);                
            }
        }
        else {
            for (int x : V[b]) {
                ans += PST.query(a, 1, r, X[x]);
            }
        }
        M[{a, b}] = ans;
        cout << ans << endl;
    }
}

Compilation message

regions.cpp: In member function 'int PST::init(int, int)':
regions.cpp:26:34: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   26 |             int ll = init(lo, lo + hi >> 1);
      |                               ~~~^~~~
regions.cpp:27:35: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   27 |             int rr = init(1 + (lo + hi >> 1), hi);
      |                                ~~~^~~~
regions.cpp: In member function 'int PST::update(int, int, int, int, int)':
regions.cpp:38:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   38 |         int mid = (lo + hi >> 1);
      |                    ~~~^~~~
regions.cpp: In member function 'int PST::query(int, int, int, int)':
regions.cpp:49:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   49 |         int mid = (lo + hi >> 1);
      |                    ~~~^~~~

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 5584 KB Output isn't correct
2 Incorrect 4 ms 5584 KB Output isn't correct
3 Incorrect 4 ms 5688 KB Output isn't correct
4 Incorrect 8 ms 5696 KB Output isn't correct
5 Incorrect 12 ms 5768 KB Output isn't correct
6 Incorrect 15 ms 5916 KB Output isn't correct
7 Incorrect 40 ms 6048 KB Output isn't correct
8 Incorrect 57 ms 6256 KB Output isn't correct
9 Incorrect 60 ms 6900 KB Output isn't correct
10 Incorrect 128 ms 7840 KB Output isn't correct
11 Incorrect 157 ms 8700 KB Output isn't correct
12 Incorrect 187 ms 9984 KB Output isn't correct
13 Incorrect 256 ms 10184 KB Output isn't correct
14 Incorrect 414 ms 11124 KB Output isn't correct
15 Incorrect 520 ms 14164 KB Output isn't correct

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 1822 ms 19536 KB Output isn't correct
2 Incorrect 1546 ms 19436 KB Output isn't correct
3 Incorrect 2928 ms 25184 KB Output isn't correct
4 Incorrect 348 ms 13580 KB Output isn't correct
5 Incorrect 419 ms 16500 KB Output isn't correct
6 Incorrect 669 ms 19052 KB Output isn't correct
7 Incorrect 996 ms 22820 KB Output isn't correct
8 Incorrect 1466 ms 34544 KB Output isn't correct
9 Incorrect 3076 ms 49408 KB Output isn't correct
10 Execution timed out 8057 ms 59304 KB Time limit exceeded
11 Execution timed out 8025 ms 60920 KB Time limit exceeded
12 Incorrect 2926 ms 55376 KB Output isn't correct
13 Incorrect 4083 ms 57476 KB Output isn't correct
14 Incorrect 4010 ms 61204 KB Output isn't correct
15 Incorrect 7413 ms 68156 KB Output isn't correct
16 Incorrect 7440 ms 71668 KB Output isn't correct
17 Incorrect 5890 ms 69260 KB Output isn't correct