Submission #516532

#	Time	Username	Problem	Language	Result	Execution time	Memory
516532		blue	Regions (IOI09_regions)	C++17	30 / 100	1116 ms	30116 KiB

regions

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vvl = vector<vl>;
#define sz(x) int(x.size())

const int maxN = 200'000;
const int maxR = 500;

vi children[1+maxN];



int N, R, Q;
vi H(1+maxN), S(1+maxN);

vvl ans(1+maxR, vl(1+maxR, 0));

vl inc(1+maxR, 0);

void dfs(int u)
{
    for(int r = 1; r <= R; r++)
        ans[r][H[u]] += inc[r];


    inc[H[u]]++;

    for(int v: children[u]) dfs(v);

    inc[H[u]]--;
}







int main()
{
    // cout << "done\n";
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> N >> R >> Q;

    cin >> H[1];
    S[1] = 0;

    for(int i = 2; i <= N; i++)
    {
        cin >> S[i] >> H[i];
        children[S[i]].push_back(i);
    }


    dfs(1);

    for(int q = 1; q <= Q; q++)
    {
        int r1, r2;
        cin >> r1 >> r2;

        cout << ans[r1][r2] << '\n';
        cout.flush();
    }

    return 0;


    // int r1, r2;
    // cin >> r1 >> r2;
    // cout << large_top[norm[r1]][r2] << '\n';
}

• Subtask 1: 15 / 15
• Subtask 2: 15 / 85