oj.uz

Submission #988536

# Submission time Handle Problem Language Result Execution time Memory
988536 2024-05-25T06:21:42 Z AC2K Regions (IOI09_regions) C++17
0 / 100
 38 ms 16088 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2 ms 8792 KB Time limit exceeded (wall clock)
2 Execution timed out 2 ms 8792 KB Time limit exceeded (wall clock)
3 Execution timed out 3 ms 8792 KB Time limit exceeded (wall clock)
4 Execution timed out 2 ms 8792 KB Time limit exceeded (wall clock)
5 Execution timed out 2 ms 8792 KB Time limit exceeded (wall clock)
6 Execution timed out 2 ms 8792 KB Time limit exceeded (wall clock)
7 Execution timed out 2 ms 8792 KB Time limit exceeded (wall clock)
8 Execution timed out 2 ms 8792 KB Time limit exceeded (wall clock)
9 Execution timed out 3 ms 8792 KB Time limit exceeded (wall clock)
10 Execution timed out 4 ms 9048 KB Time limit exceeded (wall clock)
11 Execution timed out 6 ms 9304 KB Time limit exceeded (wall clock)
12 Execution timed out 5 ms 9304 KB Time limit exceeded (wall clock)
13 Execution timed out 6 ms 9316 KB Time limit exceeded (wall clock)
14 Execution timed out 8 ms 9696 KB Time limit exceeded (wall clock)
15 Execution timed out 8 ms 10108 KB Time limit exceeded (wall clock)

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 13 ms 11532 KB Time limit exceeded (wall clock)
2 Execution timed out 19 ms 10464 KB Time limit exceeded (wall clock)
3 Execution timed out 15 ms 11968 KB Time limit exceeded (wall clock)
4 Execution timed out 8 ms 9528 KB Time limit exceeded (wall clock)
5 Execution timed out 7 ms 10072 KB Time limit exceeded (wall clock)
6 Execution timed out 11 ms 10328 KB Time limit exceeded (wall clock)
7 Execution timed out 13 ms 10712 KB Time limit exceeded (wall clock)
8 Execution timed out 18 ms 12140 KB Time limit exceeded (wall clock)
9 Execution timed out 26 ms 13656 KB Time limit exceeded (wall clock)
10 Execution timed out 30 ms 14792 KB Time limit exceeded (wall clock)
11 Execution timed out 36 ms 13172 KB Time limit exceeded (wall clock)
12 Execution timed out 35 ms 15336 KB Time limit exceeded (wall clock)
13 Execution timed out 35 ms 15252 KB Time limit exceeded (wall clock)
14 Execution timed out 36 ms 14768 KB Time limit exceeded (wall clock)
15 Execution timed out 34 ms 16020 KB Time limit exceeded (wall clock)
16 Execution timed out 38 ms 16088 KB Time limit exceeded (wall clock)
17 Execution timed out 34 ms 15784 KB Time limit exceeded (wall clock)