oj.uz

Submission #651492

# Submission time Handle Problem Language Result Execution time Memory
651492 2022-10-19T02:27:36 Z tanprodium Regions (IOI09_regions) C++14
95 / 100
 8000 ms 49736 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];
unordered_map<int, int> save[R];
unordered_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 8 ms 9424 KB Output is correct
2 Correct 6 ms 9424 KB Output is correct
3 Correct 8 ms 9424 KB Output is correct
4 Correct 9 ms 9552 KB Output is correct
5 Correct 14 ms 9552 KB Output is correct
6 Correct 27 ms 9692 KB Output is correct
7 Correct 19 ms 9856 KB Output is correct
8 Correct 40 ms 9848 KB Output is correct
9 Correct 57 ms 10436 KB Output is correct
10 Correct 99 ms 10712 KB Output is correct
11 Correct 144 ms 11188 KB Output is correct
12 Correct 161 ms 11748 KB Output is correct
13 Correct 146 ms 11864 KB Output is correct
14 Correct 308 ms 12212 KB Output is correct
15 Correct 274 ms 14908 KB Output is correct

Subtask #2
80.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1279 ms 16536 KB Output is correct
2 Correct 1561 ms 16180 KB Output is correct
3 Correct 2562 ms 20724 KB Output is correct
4 Correct 317 ms 13488 KB Output is correct
5 Correct 459 ms 15992 KB Output is correct
6 Correct 619 ms 16132 KB Output is correct
7 Correct 905 ms 16424 KB Output is correct
8 Correct 1470 ms 24324 KB Output is correct
9 Correct 2840 ms 31116 KB Output is correct
10 Correct 4534 ms 39852 KB Output is correct
11 Correct 5176 ms 40836 KB Output is correct
12 Correct 5585 ms 29092 KB Output is correct
13 Correct 6169 ms 32288 KB Output is correct
14 Correct 7446 ms 34648 KB Output is correct
15 Execution timed out 8068 ms 41940 KB Time limit exceeded
16 Correct 6053 ms 49736 KB Output is correct
17 Correct 5658 ms 45344 KB Output is correct