oj.uz

Submission #489383

# Submission time Handle Problem Language Result Execution time Memory
489383 2021-11-22T19:41:01 Z Alexandruabcde Regions (IOI09_regions) C++14
0 / 100
 352 ms 28932 KB 
#include <bits/stdc++.h>

using namespace std;

constexpr int NMAX = 2e5 + 5;
constexpr int RMAX = 25005;
constexpr int CONSTANT = 500;
typedef long long LL;

int N, R, Q;

vector <int> G[NMAX];
int H[NMAX];
int first[3*NMAX], last[3*NMAX];
int whatNode[3*NMAX];

vector <int> Region[RMAX];

int prec[CONSTANT+1][RMAX];

int cnt = 0;
int timp = 0;
int Norm[NMAX];

void Read () {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> N >> R >> Q >> H[1];

    for (int i = 2; i <= N; ++ i ) {
        int d;
        cin >> d >> H[i];

        G[d].push_back(i);
    }
}

void Precalculare (int Node, int dad = -1) {
    first[Node] = ++timp;
    whatNode[timp] = Node;
    Region[H[Node]].push_back(first[Node]);

    for (auto it : G[Node]) {
        if (it == dad) continue;

        Precalculare(it, Node);
    }
    last[Node] = ++timp;
}

void FindAnswer (int Reg, int val, int Node, int dad = -1) {
    if (H[Node] == Reg) ++ val;
    else prec[Norm[Reg]][H[Node]] += val;

    for (auto it : G[Node]) {
        if (it == dad) continue;

        FindAnswer(Reg, val, it, Node);
    }
}

void Solve () {
    for (; Q; -- Q ) {
        int x, y;
        cin >> x >> y;

        if (Region[x].size() < CONSTANT) {
            LL ans = 0;
            for (auto it : Region[x]) {
                vector <int> :: iterator st = lower_bound(Region[y].begin(), Region[y].end(), it);
                vector <int> :: iterator dr = upper_bound(Region[y].begin(), Region[y].end(), last[whatNode[it]]);

                ans += (dr - st);
            }

            cout << ans << '\n';
        }
        else {
            cout << prec[Norm[x]][y] << '\n';
        }
    }
}

int main () {
    Read();
    Precalculare(1);
    for (int i = 1; i <= R; ++ i ) {
        if (Region[i].size() < CONSTANT) continue;
        Norm[i] = ++ cnt;

        FindAnswer(i, 0, 1);
    }
    Solve();

    return 0;
}

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3 ms 5576 KB Time limit exceeded (wall clock)
2 Execution timed out 3 ms 5576 KB Time limit exceeded (wall clock)
3 Execution timed out 3 ms 5576 KB Time limit exceeded (wall clock)
4 Execution timed out 3 ms 5576 KB Time limit exceeded (wall clock)
5 Execution timed out 3 ms 5576 KB Time limit exceeded (wall clock)
6 Execution timed out 3 ms 5704 KB Time limit exceeded (wall clock)
7 Execution timed out 3 ms 5704 KB Time limit exceeded (wall clock)
8 Execution timed out 3 ms 5704 KB Time limit exceeded (wall clock)
9 Execution timed out 4 ms 6088 KB Time limit exceeded (wall clock)
10 Execution timed out 6 ms 6088 KB Time limit exceeded (wall clock)
11 Execution timed out 6 ms 6440 KB Time limit exceeded (wall clock)
12 Execution timed out 7 ms 6856 KB Time limit exceeded (wall clock)
13 Execution timed out 10 ms 6600 KB Time limit exceeded (wall clock)
14 Execution timed out 12 ms 7240 KB Time limit exceeded (wall clock)
15 Execution timed out 11 ms 9672 KB Time limit exceeded (wall clock)

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 39 ms 10688 KB Time limit exceeded (wall clock)
2 Execution timed out 43 ms 9280 KB Time limit exceeded (wall clock)
3 Execution timed out 32 ms 12744 KB Time limit exceeded (wall clock)
4 Execution timed out 10 ms 7240 KB Time limit exceeded (wall clock)
5 Execution timed out 14 ms 8812 KB Time limit exceeded (wall clock)
6 Execution timed out 37 ms 9300 KB Time limit exceeded (wall clock)
7 Execution timed out 25 ms 9616 KB Time limit exceeded (wall clock)
8 Execution timed out 39 ms 15528 KB Time limit exceeded (wall clock)
9 Execution timed out 55 ms 15108 KB Time limit exceeded (wall clock)
10 Execution timed out 46 ms 19504 KB Time limit exceeded (wall clock)
11 Execution timed out 60 ms 14912 KB Time limit exceeded (wall clock)
12 Execution timed out 103 ms 16704 KB Time limit exceeded (wall clock)
13 Execution timed out 88 ms 17088 KB Time limit exceeded (wall clock)
14 Execution timed out 352 ms 18468 KB Time limit exceeded (wall clock)
15 Execution timed out 68 ms 21596 KB Time limit exceeded (wall clock)
16 Execution timed out 65 ms 28432 KB Time limit exceeded (wall clock)
17 Execution timed out 131 ms 28932 KB Time limit exceeded (wall clock)