oj.uz

Submission #1071918

# Submission time Handle Problem Language Result Execution time Memory
1071918 2024-08-23T12:22:27 Z ArthuroWich Regions (IOI09_regions) C++17
100 / 100
 3580 ms 36940 KB 
#include <bits/stdc++.h>
using namespace std;
vector<int> adj[300005], reg[25005], regst[25005], calc[25005], re;
int act[25005], regat[300005], 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 3 ms 12632 KB Output is correct
2 Correct 3 ms 12632 KB Output is correct
3 Correct 4 ms 12632 KB Output is correct
4 Correct 5 ms 12632 KB Output is correct
5 Correct 6 ms 12632 KB Output is correct
6 Correct 11 ms 12632 KB Output is correct
7 Correct 20 ms 12632 KB Output is correct
8 Correct 19 ms 12632 KB Output is correct
9 Correct 39 ms 13144 KB Output is correct
10 Correct 53 ms 13144 KB Output is correct
11 Correct 77 ms 13392 KB Output is correct
12 Correct 111 ms 13912 KB Output is correct
13 Correct 148 ms 13656 KB Output is correct
14 Correct 210 ms 14168 KB Output is correct
15 Correct 185 ms 17752 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1538 ms 17176 KB Output is correct
2 Correct 1765 ms 16408 KB Output is correct
3 Correct 2307 ms 19280 KB Output is correct
4 Correct 180 ms 14168 KB Output is correct
5 Correct 270 ms 16472 KB Output is correct
6 Correct 384 ms 17240 KB Output is correct
7 Correct 1290 ms 16984 KB Output is correct
8 Correct 791 ms 26452 KB Output is correct
9 Correct 1855 ms 21328 KB Output is correct
10 Correct 2861 ms 32964 KB Output is correct
11 Correct 3580 ms 22608 KB Output is correct
12 Correct 975 ms 21328 KB Output is correct
13 Correct 1477 ms 22592 KB Output is correct
14 Correct 1677 ms 24236 KB Output is correct
15 Correct 2521 ms 27840 KB Output is correct
16 Correct 2421 ms 36940 KB Output is correct
17 Correct 2271 ms 36432 KB Output is correct