oj.uz

Submission #651488

# Submission time Handle Problem Language Result Execution time Memory
651488 2022-10-19T02:14:25 Z tanprodium Regions (IOI09_regions) C++14
95 / 100
 8000 ms 50452 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<pii, int> save;
map<pii, bool> exist;
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;
            fflush(stdout);
        }
        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;
        fflush(stdout);
        }
    }
}

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 4 ms 6864 KB Output is correct
2 Correct 4 ms 6736 KB Output is correct
3 Correct 6 ms 6736 KB Output is correct
4 Correct 8 ms 6736 KB Output is correct
5 Correct 12 ms 6848 KB Output is correct
6 Correct 24 ms 7028 KB Output is correct
7 Correct 38 ms 7124 KB Output is correct
8 Correct 20 ms 7228 KB Output is correct
9 Correct 63 ms 7776 KB Output is correct
10 Correct 87 ms 8260 KB Output is correct
11 Correct 136 ms 8648 KB Output is correct
12 Correct 98 ms 9416 KB Output is correct
13 Correct 237 ms 9616 KB Output is correct
14 Correct 309 ms 9868 KB Output is correct
15 Correct 304 ms 12716 KB Output is correct

Subtask #2
80.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1707 ms 14552 KB Output is correct
2 Correct 1772 ms 14384 KB Output is correct
3 Correct 2566 ms 21072 KB Output is correct
4 Correct 305 ms 11684 KB Output is correct
5 Correct 412 ms 14188 KB Output is correct
6 Correct 528 ms 13912 KB Output is correct
7 Correct 887 ms 13204 KB Output is correct
8 Correct 1406 ms 23588 KB Output is correct
9 Correct 3030 ms 32652 KB Output is correct
10 Correct 4834 ms 40556 KB Output is correct
11 Correct 5535 ms 42184 KB Output is correct
12 Correct 5207 ms 27144 KB Output is correct
13 Correct 5643 ms 32036 KB Output is correct
14 Correct 6942 ms 34752 KB Output is correct
15 Execution timed out 8068 ms 43348 KB Time limit exceeded
16 Correct 6447 ms 50452 KB Output is correct
17 Correct 5762 ms 47852 KB Output is correct