oj.uz

Submission #872517

# Submission time Handle Problem Language Result Execution time Memory
872517 2023-11-13T09:22:00 Z overwatch9 Regions (IOI09_regions) C++17
30 / 100
 2525 ms 131072 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 4 ms 8792 KB Output is correct
2 Correct 2 ms 8792 KB Output is correct
3 Correct 2 ms 8792 KB Output is correct
4 Correct 3 ms 8792 KB Output is correct
5 Correct 5 ms 8792 KB Output is correct
6 Correct 11 ms 10072 KB Output is correct
7 Correct 15 ms 9816 KB Output is correct
8 Correct 21 ms 10840 KB Output is correct
9 Correct 32 ms 15960 KB Output is correct
10 Correct 73 ms 26924 KB Output is correct
11 Correct 103 ms 26708 KB Output is correct
12 Correct 132 ms 47736 KB Output is correct
13 Correct 169 ms 43676 KB Output is correct
14 Correct 237 ms 35808 KB Output is correct
15 Correct 241 ms 54816 KB Output is correct

Subtask #2
15.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1688 ms 77244 KB Output is correct
2 Correct 1975 ms 86288 KB Output is correct
3 Correct 2525 ms 114032 KB Output is correct
4 Runtime error 65 ms 131072 KB Execution killed with signal 9
5 Runtime error 71 ms 131072 KB Execution killed with signal 9
6 Runtime error 76 ms 131072 KB Execution killed with signal 9
7 Runtime error 89 ms 131072 KB Execution killed with signal 9
8 Runtime error 101 ms 131072 KB Execution killed with signal 9
9 Runtime error 129 ms 131072 KB Execution killed with signal 9
10 Runtime error 143 ms 131072 KB Execution killed with signal 9
11 Runtime error 167 ms 131072 KB Execution killed with signal 9
12 Runtime error 161 ms 131072 KB Execution killed with signal 9
13 Runtime error 159 ms 131072 KB Execution killed with signal 9
14 Runtime error 181 ms 131072 KB Execution killed with signal 9
15 Runtime error 165 ms 131072 KB Execution killed with signal 9
16 Runtime error 159 ms 131072 KB Execution killed with signal 9
17 Runtime error 156 ms 131072 KB Execution killed with signal 9