Submission #955136

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
955136	2024-03-29T13:00:52 Z	uped	Regions (IOI09_regions)	C++14	80 / 100	8000 ms	26712 KB

regions

#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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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