Submission #1280158

#	Time	Username	Problem	Language	Result	Execution time	Memory
1280158		vk3601h	Regions (IOI09_regions)	C++20	100 / 100	2921 ms	43580 KiB

regions

#include <bits/stdc++.h>
using namespace std;

void euler_tour(vector<vector<int>> &adj, vector<int> &region, int curr, int parent, int &timer, vector<int> &start, vector<int> &end, vector<int> &time_node, vector<vector<int>> &comp){
    start[curr] = timer++;
    time_node[start[curr]] = curr;
    comp[region[curr]].push_back(start[curr]);
    for (int next : adj[curr]) if (next != parent) euler_tour(adj, region, next, curr, timer, start, end, time_node, comp);
    end[curr] = timer;
}

void dfs(vector<vector<int>> &adj, vector<int> &region, vector<int> &region_id, int curr, int parent, int parent_region, int parent_count, vector<vector<int>> &calc){
    if (region[curr] == parent_region) parent_count++;
    else calc[region_id[parent_region]][region[curr]] += parent_count;
    for (int next : adj[curr]) if (next != parent) dfs(adj, region, region_id, next, curr, parent_region, parent_count, calc);
}

int main(){
    int n, r, q;
    cin >> n >> r >> q;

    vector<int> region(n);
    vector<vector<int>> adj(n);

    cin >> region[0];
    region[0]--;
    for (int i = 1; i < n; i++){
        int parent, home;
        cin >> parent >> home;
        parent--, home--;

        region[i] = home;
        adj[i].push_back(parent);
        adj[parent].push_back(i);
    }

    int timer = 0;
    vector<int> start(n), end(n), time_node(n);
    vector<vector<int>> comp(r);
    euler_tour(adj, region, 0, -1, timer, start, end, time_node, comp);

    const int BLOCK = sqrt(n);
    vector<int> region_id(r, -1);
    vector<vector<int>> calc;

    int curr_id = 0;
    for (int i = 0; i < r; i++){
        if ((int)comp[i].size() >= BLOCK){
            region_id[i] = curr_id++;
            calc.push_back(vector<int>(r, 0));
            dfs(adj, region, region_id, 0, -1, i, 0, calc);
        }
    }

    while (q--){
        int r1, r2;
        cin >> r1 >> r2;
        r1--, r2--;

        if (region_id[r1] != -1) cout << calc[region_id[r1]][r2] << endl;
        else {
            int total = 0;
            for (int u : comp[r1]) total += lower_bound(comp[r2].begin(), comp[r2].end(), end[time_node[u]]) - lower_bound(comp[r2].begin(), comp[r2].end(), start[time_node[u]]);
            cout << total << endl;
        }
    }

    return 0;
}

• Subtask 1: 15 / 15
• Subtask 2: 85 / 85