Submission #489372

#	Time	Username	Problem	Language	Result	Execution time	Memory
489372		Alexandruabcde	Regions (IOI09_regions)	C++14	55 / 100	4826 ms	28680 KiB

regions

#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 / 15
• Subtask 2: 40 / 85