oj.uz

Submission #516497

# Submission time Handle Problem Language Result Execution time Memory
516497 2022-01-21T12:23:01 Z blue Regions (IOI09_regions) C++17
0 / 100
 200 ms 82580 KB 
#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 = 25'000;
// const int maxR = 500;

const int mns = 400;

const int maxL = 1 + maxR/mns;

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

vi region_list[1+maxR];
vi norm(1+maxR, 0);
int large_ct = 0;

vvl large_bottom(1+maxL, vl(1 + maxR));





vvl large_top(1+maxL, vl(1 + maxR));
vi inc(1+maxL, 0);

vi dfs_order(1, 0);
vi order_index(1+maxN);
int dfs_ct = 0;

vi subtree(1+maxN, 1);

void dfs(int u)
{
    dfs_order.push_back(u);
    order_index[u] = ++dfs_ct;

    for(int l = 1; l <= large_ct; l++)
        large_top[l][H[u]] += inc[l];

    if(norm[H[u]])
        inc[norm[H[u]]]++;

    for(int v: children[u])
    {
        dfs(v);
        subtree[u] += subtree[v];
    }

    if(norm[H[u]])
        inc[norm[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);
    }


    for(int i = 1; i <= N; i++)
    {
        region_list[ H[i] ].push_back(i);
    }

    for(int r = 1; r <= R; r++)
    {
        if(sz(region_list[r]) >= mns)
        {
            norm[r] = ++large_ct;
        }
    }


    dfs(1);

    vi pos_list[1+N], neg_list[1+N];
    for(int u = 1; u <= N; u++)
    {
        neg_list[order_index[u] - 1].push_back(H[u]);
        pos_list[order_index[u] + subtree[u] - 1].push_back(H[u]);
    }

    // for(int u: dfs_order) cerr << u << ' ';
    // cerr << '\n';

    // for(int r = 1; r <= R; r++)
    // {
    //     cerr << "r = " << r << " : ";
    //     for(int i = 1; i <= N)
    // }

    inc = vi(1+large_ct, 0);
    for(int i = 0; i <= N; i++)
    {
        if(norm[H[dfs_order[i]]])
            inc[ norm[H[dfs_order[i]]] ]++;

        for(int j: neg_list[i])
            for(int l = 1; l <= large_ct; l++)
                large_bottom[l][j] -= inc[l];

        for(int j: pos_list[i])
            for(int l = 1; l <= large_ct; l++)
                large_bottom[l][j] += inc[l];

        // cerr << "i = " << i << ": " << dfs_order[i] << " \n";
        // for(int r = 1; r <= R; r++) cerr << inc[r] << ' ';
        // cerr << '\n';
    }



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

        if(norm[r1]) cout << large_top[norm[r1]][r2] << '\n';
        else if(norm[r2]) cout << large_bottom[norm[r2]][r1] << '\n';
    }

    return 0;
}

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 14 ms 34052 KB Time limit exceeded (wall clock)
2 Execution timed out 14 ms 34180 KB Time limit exceeded (wall clock)
3 Execution timed out 15 ms 34052 KB Time limit exceeded (wall clock)
4 Execution timed out 14 ms 34052 KB Time limit exceeded (wall clock)
5 Execution timed out 14 ms 34068 KB Time limit exceeded (wall clock)
6 Execution timed out 14 ms 34180 KB Time limit exceeded (wall clock)
7 Execution timed out 15 ms 34248 KB Time limit exceeded (wall clock)
8 Execution timed out 15 ms 34308 KB Time limit exceeded (wall clock)
9 Execution timed out 16 ms 34820 KB Time limit exceeded (wall clock)
10 Execution timed out 22 ms 35256 KB Time limit exceeded (wall clock)
11 Execution timed out 19 ms 35844 KB Time limit exceeded (wall clock)
12 Execution timed out 24 ms 36612 KB Time limit exceeded (wall clock)
13 Execution timed out 24 ms 36996 KB Time limit exceeded (wall clock)
14 Execution timed out 27 ms 37744 KB Time limit exceeded (wall clock)
15 Execution timed out 30 ms 39652 KB Time limit exceeded (wall clock)

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 54 ms 43256 KB Time limit exceeded (wall clock)
2 Execution timed out 59 ms 43708 KB Time limit exceeded (wall clock)
3 Execution timed out 52 ms 45176 KB Time limit exceeded (wall clock)
4 Execution timed out 29 ms 37776 KB Time limit exceeded (wall clock)
5 Execution timed out 30 ms 38620 KB Time limit exceeded (wall clock)
6 Execution timed out 109 ms 40408 KB Time limit exceeded (wall clock)
7 Execution timed out 84 ms 42756 KB Time limit exceeded (wall clock)
8 Runtime error 85 ms 76736 KB Execution killed with signal 11
9 Execution timed out 90 ms 53024 KB Time limit exceeded (wall clock)
10 Runtime error 89 ms 82580 KB Execution killed with signal 11
11 Execution timed out 99 ms 58820 KB Time limit exceeded (wall clock)
12 Execution timed out 130 ms 57804 KB Time limit exceeded (wall clock)
13 Execution timed out 114 ms 57640 KB Time limit exceeded (wall clock)
14 Execution timed out 200 ms 58808 KB Time limit exceeded (wall clock)
15 Execution timed out 98 ms 59240 KB Time limit exceeded (wall clock)
16 Execution timed out 97 ms 61452 KB Time limit exceeded (wall clock)
17 Execution timed out 157 ms 60028 KB Time limit exceeded (wall clock)