oj.uz

Submission #1071915

# Submission time Handle Problem Language Result Execution time Memory
1071915 2024-08-23T12:21:17 Z ArthuroWich Regions (IOI09_regions) C++17
25 / 100
 270 ms 39504 KB 
#include <bits/stdc++.h>
using namespace std;
vector<int> adj[300005], reg[25005], regst[25005], calc[25005], re;
int act[25005], regat[25005], st[300005], en[300005], timer = 0;
void dfs(int i, int p) {
    st[i] = timer;
    timer++;
    act[regat[i]]++;
    for (int j : adj[i]) {
        if (j == p) {
            continue;
        }
        dfs(j, i);
    }
    for (int j : re) {
        calc[j][regat[i]] += act[j];
    }
    act[regat[i]]--;
    en[i] = timer;
}
void solve() {
    int n, r, q;
    cin >> n >> r >> q;
    for (int i = 1; i <= n; i++) {
        int s, h;
        if (i == 1) {
            cin >> h;
            regat[i] = h;
            reg[h].push_back(i);
        } else {
            cin >> s >> h;
            regat[i] = h;
            reg[h].push_back(i);
            adj[s].push_back(i);
            adj[i].push_back(s);
        }
    }
    for (int i = 1; i <= r; i++) {
        if (reg[i].size() > 450) {
            re.push_back(i);
            calc[i].resize(r+1, 0);
        }
    }
    dfs(1, -1);
    for (int i = 1; i <= r; i++) {
        for (int j : reg[i]) {
            regst[i].push_back(st[j]);
        }
        sort(regst[i].begin(), regst[i].end());
    }
    while(q--) {
        int a, b, ans = 0;
        cin >> a >> b;
        if (reg[a].size() <= 450) {
            for (int i : reg[a]) {
                int l, r;
                l = upper_bound(regst[b].begin(), regst[b].end(), st[i]) - regst[b].begin();
                r = lower_bound(regst[b].begin(), regst[b].end(), en[i]) - regst[b].begin();
                ans += r-l;
            }
        } else {
            ans += calc[a][b];
        }
        cout << ans << endl;
    }
}
int32_t main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t;
    t = 1;
    while(t--) {
        solve();
    }
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 11608 KB Output is correct
2 Correct 2 ms 11608 KB Output is correct
3 Correct 3 ms 11608 KB Output is correct
4 Correct 3 ms 11608 KB Output is correct
5 Correct 7 ms 11608 KB Output is correct
6 Correct 11 ms 11608 KB Output is correct
7 Correct 13 ms 11608 KB Output is correct
8 Correct 22 ms 11608 KB Output is correct
9 Correct 24 ms 12120 KB Output is correct
10 Correct 55 ms 12120 KB Output is correct
11 Correct 91 ms 12120 KB Output is correct
12 Correct 102 ms 12888 KB Output is correct
13 Correct 122 ms 12632 KB Output is correct
14 Correct 202 ms 12888 KB Output is correct
15 Correct 199 ms 16472 KB Output is correct

Subtask #2
10.0 / 85.0

# Verdict Execution time Memory Grader output
1 Runtime error 30 ms 24404 KB Execution killed with signal 11
2 Runtime error 25 ms 25168 KB Execution killed with signal 11
3 Runtime error 25 ms 25680 KB Execution killed with signal 11
4 Correct 200 ms 13144 KB Output is correct
5 Correct 270 ms 15192 KB Output is correct
6 Runtime error 19 ms 23128 KB Execution killed with signal 11
7 Runtime error 24 ms 24608 KB Execution killed with signal 11
8 Runtime error 41 ms 26876 KB Execution killed with signal 11
9 Runtime error 57 ms 35152 KB Execution killed with signal 11
10 Runtime error 43 ms 32848 KB Execution killed with signal 11
11 Runtime error 57 ms 39504 KB Execution killed with signal 11
12 Runtime error 73 ms 33360 KB Execution killed with signal 11
13 Runtime error 70 ms 33696 KB Execution killed with signal 11
14 Runtime error 59 ms 34660 KB Execution killed with signal 11
15 Runtime error 50 ms 34900 KB Execution killed with signal 11
16 Runtime error 50 ms 34640 KB Execution killed with signal 11
17 Runtime error 48 ms 34640 KB Execution killed with signal 11