oj.uz

Submission #651491

# Submission time Handle Problem Language Result Execution time Memory
651491 2022-10-19T02:25:42 Z tanprodium Regions (IOI09_regions) C++14
100 / 100
 7769 ms 46628 KB 
#include<bits/stdc++.h>

using namespace std;

using pii = pair<int, int>;

struct Queries {
    int r1, r2;

    Queries() {}
    Queries(int _r1, int _r2): r1(_r1), r2(_r2) {}
};

const int N = 2e5 + 5;
const int R = 25 * 1e3 + 5;

Queries qr[N];
vector<int> id[R], reg[R], adj[N], e[R];
map<int, int> save[R];
map<int, bool> exist[R];
int l[N], r[N];
int cnt;

void dfs(int fa, int u) {
    l[u] = ++cnt;

    for (int v : adj[u])
    if (v != fa)
        dfs(u, v);

    r[u] = cnt;
}

void solve() {
    int n, regs, q;
    cin >> n >> regs >> q;

    int x;
    cin >> x;
    reg[x].push_back(1);

    for (int i = 2; i <= n; i++) {
        int p;
        cin >> p;
        adj[i].push_back(p);
        adj[p].push_back(i);
        int h;
        cin >> h;
        reg[h].push_back(i);
    }

    cnt = 0;
    dfs(0, 1);

    for (int i = 1; i <= regs; i++) {
        for (int x : reg[i]) {
            e[i].push_back(l[x]);
        }
    }

    for (int i = 1; i <= regs; i++)
        sort(e[i].begin(), e[i].end());

    for (int i = 1; i <= q; i++) {
        int r1, r2;
        cin >> r1 >> r2;

        if (exist[r1][r2]) {
            cout << save[r1][r2] << endl;
        }
        else {

        int ans = 0;

        for (int x : reg[r1]) {
            int u = lower_bound(e[r2].begin(), e[r2].end(), l[x]) - e[r2].begin();
            int v = upper_bound(e[r2].begin(), e[r2].end(), r[x]) - e[r2].begin();
            ans += 1ll * (v - u);
        }

        exist[r1][r2] = true;
        save[r1][r2] = ans;

        cout << ans << endl;
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    solve();
    return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9060 KB Output is correct
2 Correct 5 ms 9040 KB Output is correct
3 Correct 7 ms 9040 KB Output is correct
4 Correct 7 ms 9144 KB Output is correct
5 Correct 13 ms 9208 KB Output is correct
6 Correct 26 ms 9360 KB Output is correct
7 Correct 36 ms 9444 KB Output is correct
8 Correct 41 ms 9544 KB Output is correct
9 Correct 62 ms 10044 KB Output is correct
10 Correct 71 ms 10324 KB Output is correct
11 Correct 144 ms 10832 KB Output is correct
12 Correct 171 ms 11416 KB Output is correct
13 Correct 197 ms 11592 KB Output is correct
14 Correct 218 ms 11812 KB Output is correct
15 Correct 299 ms 14424 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1605 ms 16092 KB Output is correct
2 Correct 1747 ms 15792 KB Output is correct
3 Correct 2636 ms 21288 KB Output is correct
4 Correct 244 ms 13240 KB Output is correct
5 Correct 459 ms 15692 KB Output is correct
6 Correct 632 ms 15140 KB Output is correct
7 Correct 924 ms 14960 KB Output is correct
8 Correct 1282 ms 23748 KB Output is correct
9 Correct 2784 ms 30708 KB Output is correct
10 Correct 5077 ms 37860 KB Output is correct
11 Correct 4950 ms 38260 KB Output is correct
12 Correct 5017 ms 26752 KB Output is correct
13 Correct 5581 ms 30644 KB Output is correct
14 Correct 7112 ms 32964 KB Output is correct
15 Correct 7769 ms 40548 KB Output is correct
16 Correct 5999 ms 46628 KB Output is correct
17 Correct 5909 ms 44764 KB Output is correct