Submission #988536

#	Time	Username	Problem	Language	Result	Execution time	Memory
988536		AC2K	Regions (IOI09_regions)	C++17	0 / 100	38 ms	16088 KiB

regions

#include <algorithm>
#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;

const int MAXN = 200001;
const int MAXR = 25001;
const int MAXQ = 200001;

int N, R, Q;
int regions[MAXN];
int supervisors[MAXN];
vector<int> adj[MAXN];
vector<pair<int, int>> queries;
vector<int> euler_tour;
int first_occurrence[MAXN];
int last_occurrence[MAXN];
unordered_map<int, int> region_count[MAXR];

void dfs(int node, int parent) {
    euler_tour.push_back(node);
    first_occurrence[node] = euler_tour.size() - 1;
    region_count[regions[node]][node]++;

    for (int neighbor : adj[node]) {
        if (neighbor != parent) {
            dfs(neighbor, node);
            euler_tour.push_back(node);
        }
    }

    last_occurrence[node] = euler_tour.size() - 1;
}

int count_pairs(int r1, int r2) {
    if (r1 == r2) return 0;

    int count = 0;
    for (int node = 1; node <= N; ++node) {
        if (regions[node] == r1) {
            int start = first_occurrence[node];
            int end = last_occurrence[node];
            for (int i = start; i <= end; ++i) {
                ++count;
            }
        }
    }

    return count;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> N >> R >> Q;

    cin >> regions[1];  // Chair's region
    for (int i = 2; i <= N; ++i) {
        cin >> supervisors[i] >> regions[i];
        adj[supervisors[i]].push_back(i);
    }

    for (int i = 0; i < Q; ++i) {
        int r1, r2;
        cin >> r1 >> r2;
        queries.emplace_back(r1, r2);
    }

    // Perform DFS to build Euler Tour and calculate first and last occurrences
    dfs(1, -1);

    // Process each query
    vector<int> results;
    for (auto& query : queries) {
        int r1 = query.first;
        int r2 = query.second;
        int result = count_pairs(r1, r2);
        results.push_back(result);
    }

    // Output results
    for (int result : results) {
        cout << result << "\n";
    }

    return 0;
}

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