oj.uz

Submission #489387

# Submission time Handle Problem Language Result Execution time Memory
489387 2021-11-22T19:45:29 Z Alexandruabcde Regions (IOI09_regions) C++14
100 / 100
 4540 ms 28980 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[2*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 3 ms 5576 KB Output is correct
3 Correct 4 ms 5576 KB Output is correct
4 Correct 5 ms 5576 KB Output is correct
5 Correct 10 ms 5576 KB Output is correct
6 Correct 21 ms 5576 KB Output is correct
7 Correct 31 ms 5704 KB Output is correct
8 Correct 35 ms 5704 KB Output is correct
9 Correct 52 ms 6088 KB Output is correct
10 Correct 89 ms 6088 KB Output is correct
11 Correct 118 ms 6472 KB Output is correct
12 Correct 120 ms 6856 KB Output is correct
13 Correct 174 ms 6600 KB Output is correct
14 Correct 261 ms 7240 KB Output is correct
15 Correct 275 ms 9672 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1899 ms 10720 KB Output is correct
2 Correct 2093 ms 9392 KB Output is correct
3 Correct 2743 ms 12772 KB Output is correct
4 Correct 279 ms 7240 KB Output is correct
5 Correct 371 ms 8904 KB Output is correct
6 Correct 1167 ms 9272 KB Output is correct
7 Correct 1733 ms 9560 KB Output is correct
8 Correct 1310 ms 15456 KB Output is correct
9 Correct 2087 ms 15000 KB Output is correct
10 Correct 4062 ms 19516 KB Output is correct
11 Correct 4540 ms 14896 KB Output is correct
12 Correct 1176 ms 16636 KB Output is correct
13 Correct 2041 ms 17212 KB Output is correct
14 Correct 2368 ms 18488 KB Output is correct
15 Correct 2857 ms 21588 KB Output is correct
16 Correct 3089 ms 28492 KB Output is correct
17 Correct 2807 ms 28980 KB Output is correct