oj.uz

Submission #651489

# Submission time Handle Problem Language Result Execution time Memory
651489 2022-10-19T02:17:02 Z tanprodium Regions (IOI09_regions) C++14
75 / 100
 8000 ms 26316 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];
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;

        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);
        }

        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 5 ms 6736 KB Output is correct
2 Correct 5 ms 6736 KB Output is correct
3 Correct 5 ms 6736 KB Output is correct
4 Correct 7 ms 6736 KB Output is correct
5 Correct 9 ms 6736 KB Output is correct
6 Correct 25 ms 6864 KB Output is correct
7 Correct 32 ms 6864 KB Output is correct
8 Correct 40 ms 6864 KB Output is correct
9 Correct 48 ms 7248 KB Output is correct
10 Correct 47 ms 7248 KB Output is correct
11 Correct 128 ms 7524 KB Output is correct
12 Correct 119 ms 8016 KB Output is correct
13 Correct 157 ms 8016 KB Output is correct
14 Correct 313 ms 8320 KB Output is correct
15 Correct 272 ms 10704 KB Output is correct

Subtask #2
60.0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8085 ms 11148 KB Time limit exceeded
2 Execution timed out 8074 ms 10848 KB Time limit exceeded
3 Execution timed out 8087 ms 12752 KB Time limit exceeded
4 Correct 298 ms 8528 KB Output is correct
5 Correct 368 ms 9820 KB Output is correct
6 Correct 1262 ms 9672 KB Output is correct
7 Correct 1761 ms 10788 KB Output is correct
8 Correct 1131 ms 15424 KB Output is correct
9 Correct 2355 ms 15888 KB Output is correct
10 Correct 4090 ms 20424 KB Output is correct
11 Correct 4228 ms 18124 KB Output is correct
12 Correct 5111 ms 16656 KB Output is correct
13 Correct 5345 ms 17440 KB Output is correct
14 Correct 7621 ms 17744 KB Output is correct
15 Execution timed out 8063 ms 20836 KB Time limit exceeded
16 Correct 6002 ms 26316 KB Output is correct
17 Execution timed out 8036 ms 25072 KB Time limit exceeded