oj.uz

Submission #489372

# Submission time Handle Problem Language Result Execution time Memory
489372 2021-11-22T18:44:53 Z Alexandruabcde Regions (IOI09_regions) C++14
55 / 100
 4826 ms 28680 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[NMAX], last[NMAX];
int whatNode[NMAX];

vector <int> Region[RMAX];

int prec[CONSTANT+1][RMAX];

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) {
            LL 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 3 ms 5576 KB Output is correct
2 Correct 4 ms 5576 KB Output is correct
3 Correct 5 ms 5576 KB Output is correct
4 Correct 7 ms 5576 KB Output is correct
5 Correct 10 ms 5576 KB Output is correct
6 Correct 23 ms 5704 KB Output is correct
7 Correct 33 ms 5704 KB Output is correct
8 Correct 28 ms 5704 KB Output is correct
9 Correct 47 ms 6088 KB Output is correct
10 Correct 86 ms 6088 KB Output is correct
11 Correct 104 ms 6472 KB Output is correct
12 Correct 137 ms 6856 KB Output is correct
13 Correct 110 ms 6600 KB Output is correct
14 Correct 259 ms 7232 KB Output is correct
15 Correct 261 ms 9556 KB Output is correct

Subtask #2
40.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1865 ms 10712 KB Output is correct
2 Correct 1968 ms 9400 KB Output is correct
3 Correct 2638 ms 12780 KB Output is correct
4 Correct 280 ms 7240 KB Output is correct
5 Correct 328 ms 8776 KB Output is correct
6 Correct 1091 ms 9152 KB Output is correct
7 Correct 1605 ms 9548 KB Output is correct
8 Correct 1315 ms 15520 KB Output is correct
9 Incorrect 2140 ms 14576 KB Output isn't correct
10 Incorrect 4776 ms 19112 KB Output isn't correct
11 Incorrect 4826 ms 14120 KB Output isn't correct
12 Incorrect 1538 ms 15952 KB Output isn't correct
13 Incorrect 2298 ms 16560 KB Output isn't correct
14 Incorrect 2788 ms 17716 KB Output isn't correct
15 Incorrect 3791 ms 21048 KB Output isn't correct
16 Incorrect 2901 ms 28392 KB Output isn't correct
17 Incorrect 2814 ms 28680 KB Output isn't correct