oj.uz

Submission #516498

# Submission time Handle Problem Language Result Execution time Memory
516498 2022-01-21T12:23:16 Z blue Regions (IOI09_regions) C++17
0 / 100
 217 ms 82672 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';



        cout.flush();
    }

    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 13 ms 34052 KB Time limit exceeded (wall clock)
3 Execution timed out 13 ms 34052 KB Time limit exceeded (wall clock)
4 Execution timed out 14 ms 34044 KB Time limit exceeded (wall clock)
5 Execution timed out 18 ms 34060 KB Time limit exceeded (wall clock)
6 Execution timed out 14 ms 34172 KB Time limit exceeded (wall clock)
7 Execution timed out 14 ms 34180 KB Time limit exceeded (wall clock)
8 Execution timed out 18 ms 34308 KB Time limit exceeded (wall clock)
9 Execution timed out 16 ms 34708 KB Time limit exceeded (wall clock)
10 Execution timed out 17 ms 35304 KB Time limit exceeded (wall clock)
11 Execution timed out 21 ms 35940 KB Time limit exceeded (wall clock)
12 Execution timed out 21 ms 36592 KB Time limit exceeded (wall clock)
13 Execution timed out 24 ms 36936 KB Time limit exceeded (wall clock)
14 Execution timed out 31 ms 37700 KB Time limit exceeded (wall clock)
15 Execution timed out 34 ms 39596 KB Time limit exceeded (wall clock)

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 61 ms 43312 KB Time limit exceeded (wall clock)
2 Execution timed out 64 ms 43780 KB Time limit exceeded (wall clock)
3 Execution timed out 53 ms 45192 KB Time limit exceeded (wall clock)
4 Execution timed out 27 ms 37828 KB Time limit exceeded (wall clock)
5 Execution timed out 28 ms 38640 KB Time limit exceeded (wall clock)
6 Execution timed out 112 ms 40516 KB Time limit exceeded (wall clock)
7 Execution timed out 82 ms 42788 KB Time limit exceeded (wall clock)
8 Runtime error 74 ms 76656 KB Execution killed with signal 11
9 Execution timed out 75 ms 52968 KB Time limit exceeded (wall clock)
10 Runtime error 112 ms 82672 KB Execution killed with signal 11
11 Execution timed out 101 ms 58764 KB Time limit exceeded (wall clock)
12 Execution timed out 115 ms 57836 KB Time limit exceeded (wall clock)
13 Execution timed out 106 ms 57700 KB Time limit exceeded (wall clock)
14 Execution timed out 182 ms 58764 KB Time limit exceeded (wall clock)
15 Execution timed out 94 ms 59220 KB Time limit exceeded (wall clock)
16 Execution timed out 96 ms 61404 KB Time limit exceeded (wall clock)
17 Execution timed out 217 ms 60072 KB Time limit exceeded (wall clock)