oj.uz

Submission #955149

# Submission time Handle Problem Language Result Execution time Memory
955149 2024-03-29T13:27:30 Z uped Regions (IOI09_regions) C++14
100 / 100
 3534 ms 60956 KB 
#include <bits/stdc++.h>

#define DEBUG(x) cout << #x << ": " << x << '\n';

using namespace std;
using ll = long long;

const int N = 2e5;
const int R = 25001;

vector<int> adj[N];
int region[N];
int timer = 0;
int tin[N];
int tout[N];
vector<int> region_tin[R];
vector<int> region_nodes[R];
int region_size[R];

void tour(int n, int p = -1) {
    tin[n] = timer++;
    region_tin[region[n]].push_back(tin[n]);
    for (int x : adj[n]) {
        if (x == p) continue;
        tour(x, n);
    }
    tout[n] = timer++;
}

map<pair<int, int>, int> precalc_ans;

void precalc(int r, int n, int p = -1, int cnt = 0) {
    if (region[n] != r) precalc_ans[{r, region[n]}] += cnt;
    for (int x : adj[n]) {
        if (x == p) continue;
        precalc(r, x, n, cnt + (region[n] == r));
    }
    
}

int main() {
    int n, r, q;
    cin >> n >> r >> q;
    cin >> region[0];
    region_nodes[region[0]].push_back(0);
    region_size[region[0]]++;
    for (int i = 1; i < n; ++i) {
        int p;
        cin >> p >> region[i];
        region_size[region[i]]++;
        region_nodes[region[i]].push_back(i);
        adj[p - 1].push_back(i);
    }
    tour(0);
    for (int i = 1; i <= r; ++i) {
        if (region_size[i] > 500) precalc(i, 0);
    }

    for (int i = 0; i < q; ++i) {
        int a, b;
        cin >> a >> b;
        int ans = 0;
        if (region_size[a] <= 500) {
            for (int node : region_nodes[a]) {
                ans += upper_bound(region_tin[b].begin(), region_tin[b].end(), tout[node]) - lower_bound(region_tin[b].begin(), region_tin[b].end(), tin[node]);
            }
        } else {
            ans = precalc_ans[make_pair(a, b)];
        }
       
        cout << ans << endl;
    }
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8536 KB Output is correct
2 Correct 2 ms 8536 KB Output is correct
3 Correct 3 ms 8536 KB Output is correct
4 Correct 4 ms 8536 KB Output is correct
5 Correct 6 ms 8536 KB Output is correct
6 Correct 10 ms 8536 KB Output is correct
7 Correct 16 ms 8536 KB Output is correct
8 Correct 19 ms 8536 KB Output is correct
9 Correct 29 ms 9048 KB Output is correct
10 Correct 46 ms 9044 KB Output is correct
11 Correct 95 ms 9292 KB Output is correct
12 Correct 99 ms 9608 KB Output is correct
13 Correct 117 ms 9332 KB Output is correct
14 Correct 218 ms 9772 KB Output is correct
15 Correct 215 ms 12176 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1463 ms 13364 KB Output is correct
2 Correct 1648 ms 11380 KB Output is correct
3 Correct 2225 ms 16180 KB Output is correct
4 Correct 207 ms 9836 KB Output is correct
5 Correct 312 ms 11328 KB Output is correct
6 Correct 1115 ms 10728 KB Output is correct
7 Correct 1310 ms 11708 KB Output is correct
8 Correct 991 ms 16240 KB Output is correct
9 Correct 1763 ms 16376 KB Output is correct
10 Correct 3534 ms 20980 KB Output is correct
11 Correct 3365 ms 15728 KB Output is correct
12 Correct 1112 ms 18944 KB Output is correct
13 Correct 1517 ms 20172 KB Output is correct
14 Correct 2289 ms 41572 KB Output is correct
15 Correct 2548 ms 28836 KB Output is correct
16 Correct 2337 ms 41620 KB Output is correct
17 Correct 2847 ms 60956 KB Output is correct