oj.uz

답안 #955136

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
955136 2024-03-29T13:00:52 Z uped Regions (IOI09_regions) C++14
80 / 100
 8000 ms 26712 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];

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++;
}

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

    for (int i = 0; i < q; ++i) {
        int a, b;
        cin >> a >> b;
        int ans = 0;
        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]);
        }
        cout << ans << endl;
    }
}

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 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 11 ms 8620 KB Output is correct
7 Correct 20 ms 8536 KB Output is correct
8 Correct 17 ms 8536 KB Output is correct
9 Correct 33 ms 9048 KB Output is correct
10 Correct 53 ms 9048 KB Output is correct
11 Correct 93 ms 9304 KB Output is correct
12 Correct 91 ms 9536 KB Output is correct
13 Correct 133 ms 9264 KB Output is correct
14 Correct 192 ms 9808 KB Output is correct
15 Correct 199 ms 12216 KB Output is correct

Subtask #2
65.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 8071 ms 12252 KB Time limit exceeded
2 Execution timed out 8087 ms 10936 KB Time limit exceeded
3 Execution timed out 8031 ms 13892 KB Time limit exceeded
4 Correct 185 ms 9748 KB Output is correct
5 Correct 254 ms 11328 KB Output is correct
6 Correct 1115 ms 10808 KB Output is correct
7 Correct 1322 ms 11548 KB Output is correct
8 Correct 973 ms 16376 KB Output is correct
9 Correct 1728 ms 16292 KB Output is correct
10 Correct 3491 ms 20952 KB Output is correct
11 Correct 3403 ms 15476 KB Output is correct
12 Correct 4521 ms 16828 KB Output is correct
13 Correct 4836 ms 17380 KB Output is correct
14 Correct 6767 ms 17016 KB Output is correct
15 Correct 7318 ms 21396 KB Output is correct
16 Correct 5547 ms 26712 KB Output is correct
17 Execution timed out 8034 ms 25288 KB Time limit exceeded