oj.uz

Submission #872519

# Submission time Handle Problem Language Result Execution time Memory
872519 2023-11-13T09:24:39 Z overwatch9 Regions (IOI09_regions) C++17
100 / 100
 3982 ms 66764 KB 
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int maxn = 2e5 + 10;
const int maxr = 25000 + 10;
vector <int> adj[maxn];
int region[maxn];
vector <int> region_members[maxr];
int visit[maxn], finish[maxn];
int n, r, q, t = 0;
void dfs(int s) {
    visit[s] = t++;
    for (auto i : adj[s])
        dfs(i);
    finish[s] = t++;
}
vector <vector <int>> r1r2, cnt;
int big_region_cnt = 0;
int big_id[maxn];
void dfs2(int s, int p) {
    int id1 = big_id[region[s]];
    int id2 = big_id[region[p]];
    cnt[s] = cnt[p];
    if (id2 != -1 && s != p)
        cnt[s][id2]++;
    if (id1 != -1) {
        for (int i = 0; i < big_region_cnt; i++)
            r1r2[i][id1] += cnt[s][i];
    }
    for (auto i : adj[s])
        dfs2(i, s);
}
int main() {
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    cin >> n >> r >> q;
    cin >> region[1];
    region_members[region[1]].push_back(1);
    for (int i = 2; i <= n; i++) {
        int x;
        cin >> x;
        adj[x].push_back(i);
        cin >> region[i];
        region_members[region[i]].push_back(i);
    }
    dfs(1);
    vector <vector <int>> starts(r+1);
    for (int i = 1; i <= r; i++) {
        for (auto j : region_members[i])
            starts[i].push_back(visit[j]);
        sort(starts[i].begin(), starts[i].end());
    }
    fill(big_id, big_id + maxn, -1);
    for (int i = 1; i <= r; i++) {
        if (region_members[i].size() > 500)
            big_id[i] = big_region_cnt++;
    }

    r1r2 = vector <vector <int>> (big_region_cnt + 10, vector <int> (big_region_cnt + 10));
    cnt = vector <vector <int>> (n+1, vector <int> (big_region_cnt + 10));
    dfs2(1, 1);

    while (q--) {
        int r1, r2;
        cin >> r1 >> r2;
        if (region_members[r1].size() <= 500) { // small
            int ans = 0;
            for (auto i : region_members[r1]) {
                auto l = upper_bound(starts[r2].begin(), starts[r2].end(), visit[i]) - starts[r2].begin();
                auto r = upper_bound(starts[r2].begin(), starts[r2].end(), finish[i]) - starts[r2].begin();
                ans += max(0, (int)(r - l));
            }
            cout << ans << endl;
        } else if (region_members[r2].size() <= 500) { // small
            int ans = 0;
            for (auto i : region_members[r2]) {
                ans += cnt[i][big_id[r1]];
            }
            cout << ans << endl;
        } else {
            cout << r1r2[big_id[r1]][big_id[r2]] << endl;
        }
    }

}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8792 KB Output is correct
2 Correct 2 ms 8792 KB Output is correct
3 Correct 3 ms 8792 KB Output is correct
4 Correct 5 ms 8792 KB Output is correct
5 Correct 5 ms 8792 KB Output is correct
6 Correct 11 ms 8792 KB Output is correct
7 Correct 15 ms 8792 KB Output is correct
8 Correct 17 ms 9048 KB Output is correct
9 Correct 30 ms 9816 KB Output is correct
10 Correct 50 ms 9816 KB Output is correct
11 Correct 80 ms 10404 KB Output is correct
12 Correct 98 ms 11460 KB Output is correct
13 Correct 129 ms 11188 KB Output is correct
14 Correct 218 ms 12100 KB Output is correct
15 Correct 203 ms 17024 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1638 ms 22156 KB Output is correct
2 Correct 1871 ms 21916 KB Output is correct
3 Correct 2452 ms 26184 KB Output is correct
4 Correct 202 ms 12356 KB Output is correct
5 Correct 249 ms 15508 KB Output is correct
6 Correct 1205 ms 15212 KB Output is correct
7 Correct 1443 ms 17332 KB Output is correct
8 Correct 1047 ms 27096 KB Output is correct
9 Correct 1981 ms 28264 KB Output is correct
10 Correct 3791 ms 37952 KB Output is correct
11 Correct 3982 ms 30496 KB Output is correct
12 Correct 1170 ms 34120 KB Output is correct
13 Correct 1684 ms 35048 KB Output is correct
14 Correct 1846 ms 50816 KB Output is correct
15 Correct 2757 ms 42496 KB Output is correct
16 Correct 2439 ms 53572 KB Output is correct
17 Correct 2313 ms 66764 KB Output is correct