Submission #516512

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
516512	2022-01-21T12:40:58 Z	blue	Regions (IOI09_regions)	C++17	30 / 100	1327 ms	30104 KB

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

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	8520 KB	Output is correct
2	Correct	5 ms	8520 KB	Output is correct
3	Correct	6 ms	8520 KB	Output is correct
4	Correct	7 ms	8520 KB	Output is correct
5	Correct	8 ms	8600 KB	Output is correct
6	Correct	30 ms	8600 KB	Output is correct
7	Correct	30 ms	8520 KB	Output is correct
8	Correct	30 ms	8620 KB	Output is correct
9	Correct	54 ms	8776 KB	Output is correct
10	Correct	68 ms	8852 KB	Output is correct
11	Correct	105 ms	9040 KB	Output is correct
12	Correct	142 ms	9324 KB	Output is correct
13	Correct	107 ms	8956 KB	Output is correct
14	Correct	153 ms	9372 KB	Output is correct
15	Correct	194 ms	11064 KB	Output is correct

Subtask #2

15.0 / 85.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	636 ms	11264 KB	Output is correct
2	Correct	623 ms	10180 KB	Output is correct
3	Correct	1327 ms	12452 KB	Output is correct
4	Runtime error	19 ms	18664 KB	Execution killed with signal 11
5	Runtime error	21 ms	19500 KB	Execution killed with signal 11
6	Runtime error	31 ms	19824 KB	Execution killed with signal 11
7	Runtime error	27 ms	20824 KB	Execution killed with signal 11
8	Runtime error	35 ms	23664 KB	Execution killed with signal 11
9	Runtime error	65 ms	26084 KB	Execution killed with signal 11
10	Runtime error	49 ms	28224 KB	Execution killed with signal 11
11	Runtime error	76 ms	24428 KB	Execution killed with signal 11
12	Runtime error	72 ms	29116 KB	Execution killed with signal 11
13	Runtime error	72 ms	28016 KB	Execution killed with signal 11
14	Runtime error	61 ms	27748 KB	Execution killed with signal 11
15	Runtime error	60 ms	30100 KB	Execution killed with signal 11
16	Runtime error	79 ms	30104 KB	Execution killed with signal 11
17	Runtime error	62 ms	29972 KB	Execution killed with signal 11