oj.uz

Submission #516494

# Submission time Handle Problem Language Result Execution time Memory
516494 2022-01-21T12:18:32 Z blue Regions (IOI09_regions) C++17
0 / 100
 255 ms 37112 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 = 500;

const int mns = 1;

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;

        cout << large_bottom[norm[r2]][r1] << '\n';
    }

    return 0;


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

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5 ms 12104 KB Time limit exceeded (wall clock)
2 Execution timed out 5 ms 12104 KB Time limit exceeded (wall clock)
3 Execution timed out 5 ms 12104 KB Time limit exceeded (wall clock)
4 Execution timed out 6 ms 12104 KB Time limit exceeded (wall clock)
5 Execution timed out 6 ms 12104 KB Time limit exceeded (wall clock)
6 Execution timed out 7 ms 12232 KB Time limit exceeded (wall clock)
7 Execution timed out 8 ms 12232 KB Time limit exceeded (wall clock)
8 Execution timed out 10 ms 12372 KB Time limit exceeded (wall clock)
9 Execution timed out 21 ms 12744 KB Time limit exceeded (wall clock)
10 Execution timed out 47 ms 13384 KB Time limit exceeded (wall clock)
11 Execution timed out 47 ms 13896 KB Time limit exceeded (wall clock)
12 Execution timed out 103 ms 14596 KB Time limit exceeded (wall clock)
13 Execution timed out 100 ms 15024 KB Time limit exceeded (wall clock)
14 Execution timed out 68 ms 15816 KB Time limit exceeded (wall clock)
15 Execution timed out 99 ms 17716 KB Time limit exceeded (wall clock)

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 165 ms 21316 KB Time limit exceeded (wall clock)
2 Execution timed out 189 ms 21716 KB Time limit exceeded (wall clock)
3 Execution timed out 255 ms 23108 KB Time limit exceeded (wall clock)
4 Runtime error 22 ms 26056 KB Execution killed with signal 6
5 Runtime error 26 ms 26740 KB Execution killed with signal 6
6 Runtime error 31 ms 27204 KB Execution killed with signal 6
7 Runtime error 31 ms 28164 KB Execution killed with signal 6
8 Runtime error 43 ms 30776 KB Execution killed with signal 6
9 Runtime error 54 ms 33252 KB Execution killed with signal 6
10 Runtime error 54 ms 35264 KB Execution killed with signal 6
11 Runtime error 58 ms 31744 KB Execution killed with signal 6
12 Runtime error 56 ms 36256 KB Execution killed with signal 6
13 Runtime error 58 ms 35276 KB Execution killed with signal 6
14 Runtime error 60 ms 34876 KB Execution killed with signal 6
15 Runtime error 59 ms 36988 KB Execution killed with signal 6
16 Runtime error 58 ms 37112 KB Execution killed with signal 6
17 Runtime error 59 ms 37104 KB Execution killed with signal 6