Submission #516532

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
516532	2022-01-21T12:51:55 Z	blue	Regions (IOI09_regions)	C++17	30 / 100	1116 ms	30116 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	4 ms	8520 KB	Output is correct
2	Correct	4 ms	8580 KB	Output is correct
3	Correct	7 ms	8520 KB	Output is correct
4	Correct	12 ms	8520 KB	Output is correct
5	Correct	12 ms	8580 KB	Output is correct
6	Correct	22 ms	8520 KB	Output is correct
7	Correct	37 ms	8520 KB	Output is correct
8	Correct	35 ms	8520 KB	Output is correct
9	Correct	47 ms	8868 KB	Output is correct
10	Correct	106 ms	8832 KB	Output is correct
11	Correct	104 ms	9036 KB	Output is correct
12	Correct	161 ms	9320 KB	Output is correct
13	Correct	157 ms	8952 KB	Output is correct
14	Correct	197 ms	9384 KB	Output is correct
15	Correct	216 ms	11068 KB	Output is correct

Subtask #2

15.0 / 85.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	802 ms	11252 KB	Output is correct
2	Correct	864 ms	10176 KB	Output is correct
3	Correct	1116 ms	12452 KB	Output is correct
4	Runtime error	27 ms	18728 KB	Execution killed with signal 11
5	Runtime error	23 ms	19552 KB	Execution killed with signal 11
6	Runtime error	32 ms	19776 KB	Execution killed with signal 11
7	Runtime error	26 ms	20816 KB	Execution killed with signal 11
8	Runtime error	42 ms	23636 KB	Execution killed with signal 11
9	Runtime error	51 ms	26004 KB	Execution killed with signal 11
10	Runtime error	51 ms	28152 KB	Execution killed with signal 11
11	Runtime error	56 ms	24464 KB	Execution killed with signal 11
12	Runtime error	77 ms	29120 KB	Execution killed with signal 11
13	Runtime error	67 ms	27968 KB	Execution killed with signal 11
14	Runtime error	75 ms	27796 KB	Execution killed with signal 11
15	Runtime error	60 ms	30116 KB	Execution killed with signal 11
16	Runtime error	62 ms	30024 KB	Execution killed with signal 11
17	Runtime error	67 ms	30088 KB	Execution killed with signal 11