oj.uz

Submission #651490

# Submission time Handle Problem Language Result Execution time Memory
651490 2022-10-19T02:23:01 Z tanprodium Regions (IOI09_regions) C++14
1 / 100
 7939 ms 55828 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[N];
map<int, bool> exist[N];
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[r2][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
1.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 25552 KB Output is correct
2 Incorrect 14 ms 25544 KB Output isn't correct
3 Incorrect 15 ms 25552 KB Output isn't correct
4 Incorrect 17 ms 25600 KB Output isn't correct
5 Incorrect 21 ms 25628 KB Output isn't correct
6 Incorrect 21 ms 25744 KB Output isn't correct
7 Incorrect 45 ms 25680 KB Output isn't correct
8 Incorrect 49 ms 25728 KB Output isn't correct
9 Incorrect 63 ms 26252 KB Output isn't correct
10 Incorrect 55 ms 26456 KB Output isn't correct
11 Incorrect 130 ms 26840 KB Output isn't correct
12 Incorrect 174 ms 27340 KB Output isn't correct
13 Incorrect 209 ms 27536 KB Output isn't correct
14 Incorrect 315 ms 27808 KB Output isn't correct
15 Incorrect 291 ms 30304 KB Output isn't correct

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 1511 ms 31968 KB Output isn't correct
2 Incorrect 1743 ms 31708 KB Output isn't correct
3 Incorrect 2314 ms 36076 KB Output isn't correct
4 Incorrect 300 ms 28596 KB Output isn't correct
5 Incorrect 410 ms 30556 KB Output isn't correct
6 Incorrect 637 ms 30908 KB Output isn't correct
7 Incorrect 912 ms 31460 KB Output isn't correct
8 Incorrect 1094 ms 38540 KB Output isn't correct
9 Incorrect 2481 ms 41604 KB Output isn't correct
10 Incorrect 4320 ms 48288 KB Output isn't correct
11 Incorrect 5037 ms 47404 KB Output isn't correct
12 Incorrect 4806 ms 40292 KB Output isn't correct
13 Incorrect 5874 ms 42524 KB Output isn't correct
14 Incorrect 6698 ms 44408 KB Output isn't correct
15 Incorrect 7939 ms 49732 KB Output isn't correct
16 Incorrect 6393 ms 55828 KB Output isn't correct
17 Incorrect 5838 ms 53860 KB Output isn't correct