oj.uz

Submission #489371

# Submission time Handle Problem Language Result Execution time Memory
489371 2021-11-22T18:28:15 Z Alexandruabcde Regions (IOI09_regions) C++14
55 / 100
 4772 ms 37520 KB 
#include <bits/stdc++.h>

using namespace std;

constexpr int NMAX = 2e5 + 5;
constexpr int CONSTANT = 500;

int N, R, Q;

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

vector <int> Region[NMAX];

int prec[CONSTANT+1][NMAX];

int cnt = 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);
    }
}

int timp = 0;

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) {
            int ans = 0;
            for (auto it : Region[x]) {
                vector <int> :: iterator st = lower_bound(Region[y].begin(), Region[y].end(), first[whatNode[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';
        }
        cout.flush();
    }
}

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
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14408 KB Output is correct
2 Correct 9 ms 14408 KB Output is correct
3 Correct 12 ms 14408 KB Output is correct
4 Correct 14 ms 14408 KB Output is correct
5 Correct 15 ms 14420 KB Output is correct
6 Correct 27 ms 14408 KB Output is correct
7 Correct 37 ms 14408 KB Output is correct
8 Correct 43 ms 14536 KB Output is correct
9 Correct 37 ms 14892 KB Output is correct
10 Correct 69 ms 14920 KB Output is correct
11 Correct 121 ms 15176 KB Output is correct
12 Correct 150 ms 15688 KB Output is correct
13 Correct 162 ms 15432 KB Output is correct
14 Correct 248 ms 15992 KB Output is correct
15 Correct 185 ms 18504 KB Output is correct

Subtask #2
40.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1717 ms 19560 KB Output is correct
2 Correct 2009 ms 18240 KB Output is correct
3 Correct 2758 ms 21612 KB Output is correct
4 Correct 223 ms 16072 KB Output is correct
5 Correct 364 ms 17588 KB Output is correct
6 Correct 1032 ms 18076 KB Output is correct
7 Correct 1612 ms 18344 KB Output is correct
8 Correct 1318 ms 24256 KB Output is correct
9 Incorrect 2138 ms 23316 KB Output isn't correct
10 Incorrect 4161 ms 27940 KB Output isn't correct
11 Incorrect 4772 ms 22924 KB Output isn't correct
12 Incorrect 1465 ms 24784 KB Output isn't correct
13 Incorrect 2111 ms 25208 KB Output isn't correct
14 Incorrect 2524 ms 26544 KB Output isn't correct
15 Incorrect 3405 ms 29888 KB Output isn't correct
16 Incorrect 3340 ms 37248 KB Output isn't correct
17 Incorrect 2747 ms 37520 KB Output isn't correct