oj.uz

Submission #607149

# Submission time Handle Problem Language Result Execution time Memory
607149 2022-07-26T12:30:31 Z jhwest2 Regions (IOI09_regions) C++14
0 / 100
 8000 ms 73840 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], W[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;
        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() {
    cout.tie(0); ios_base::sync_with_stdio(0);
    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]]);
    }

    dfs(1);
    for (int i = 1; i <= n; i++) {
        W[R[i]].push_back(LL[i]);
    }
    for (int i = 1; i <= r; i++) {
        sort(W[i].begin(), W[i].end());
    }
    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 += upper_bound(W[b].begin(), W[b].end(), RR[x]) -
                    lower_bound(W[b].begin(), W[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:48:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   48 |         int mid = (lo + hi >> 1);
      |                    ~~~^~~~

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 6224 KB Output isn't correct
2 Incorrect 4 ms 6224 KB Output isn't correct
3 Incorrect 7 ms 6292 KB Output isn't correct
4 Incorrect 8 ms 6224 KB Output isn't correct
5 Incorrect 15 ms 6400 KB Output isn't correct
6 Incorrect 22 ms 6480 KB Output isn't correct
7 Incorrect 32 ms 6608 KB Output isn't correct
8 Incorrect 40 ms 6808 KB Output isn't correct
9 Incorrect 65 ms 7588 KB Output isn't correct
10 Incorrect 119 ms 8420 KB Output isn't correct
11 Incorrect 114 ms 9308 KB Output isn't correct
12 Incorrect 162 ms 10724 KB Output isn't correct
13 Incorrect 236 ms 10928 KB Output isn't correct
14 Incorrect 251 ms 11868 KB Output isn't correct
15 Incorrect 331 ms 15036 KB Output isn't correct

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 1923 ms 20632 KB Output isn't correct
2 Incorrect 1861 ms 20372 KB Output isn't correct
3 Incorrect 2611 ms 26188 KB Output isn't correct
4 Incorrect 197 ms 14340 KB Output isn't correct
5 Incorrect 507 ms 17352 KB Output isn't correct
6 Incorrect 655 ms 20160 KB Output isn't correct
7 Incorrect 887 ms 23868 KB Output isn't correct
8 Incorrect 1826 ms 35920 KB Output isn't correct
9 Incorrect 3537 ms 51340 KB Output isn't correct
10 Execution timed out 8048 ms 60244 KB Time limit exceeded
11 Execution timed out 8019 ms 66052 KB Time limit exceeded
12 Incorrect 2579 ms 57264 KB Output isn't correct
13 Incorrect 3625 ms 59296 KB Output isn't correct
14 Incorrect 4295 ms 63132 KB Output isn't correct
15 Execution timed out 8048 ms 70200 KB Time limit exceeded
16 Execution timed out 8029 ms 73840 KB Time limit exceeded
17 Incorrect 7264 ms 71304 KB Output isn't correct