oj.uz

Submission #516493

# Submission time Handle Problem Language Result Execution time Memory
516493 2022-01-21T12:17:02 Z blue Regions (IOI09_regions) C++17
0 / 100
 244 ms 37104 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_top[norm[r1]][r2] << '\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 6 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 6 ms 12068 KB Time limit exceeded (wall clock)
4 Execution timed out 5 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 9 ms 12360 KB Time limit exceeded (wall clock)
9 Execution timed out 20 ms 12744 KB Time limit exceeded (wall clock)
10 Execution timed out 48 ms 13248 KB Time limit exceeded (wall clock)
11 Execution timed out 45 ms 13888 KB Time limit exceeded (wall clock)
12 Execution timed out 99 ms 14548 KB Time limit exceeded (wall clock)
13 Execution timed out 89 ms 14976 KB Time limit exceeded (wall clock)
14 Execution timed out 67 ms 15808 KB Time limit exceeded (wall clock)
15 Execution timed out 97 ms 17636 KB Time limit exceeded (wall clock)

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 164 ms 21348 KB Time limit exceeded (wall clock)
2 Execution timed out 182 ms 21744 KB Time limit exceeded (wall clock)
3 Execution timed out 244 ms 23224 KB Time limit exceeded (wall clock)
4 Runtime error 27 ms 25992 KB Execution killed with signal 6
5 Runtime error 24 ms 26720 KB Execution killed with signal 6
6 Runtime error 29 ms 27120 KB Execution killed with signal 6
7 Runtime error 34 ms 28148 KB Execution killed with signal 6
8 Runtime error 41 ms 30872 KB Execution killed with signal 6
9 Runtime error 55 ms 33332 KB Execution killed with signal 6
10 Runtime error 59 ms 35312 KB Execution killed with signal 6
11 Runtime error 67 ms 31728 KB Execution killed with signal 6
12 Runtime error 63 ms 36204 KB Execution killed with signal 6
13 Runtime error 82 ms 35360 KB Execution killed with signal 6
14 Runtime error 62 ms 34920 KB Execution killed with signal 6
15 Runtime error 68 ms 37044 KB Execution killed with signal 6
16 Runtime error 65 ms 37104 KB Execution killed with signal 6
17 Runtime error 63 ms 37100 KB Execution killed with signal 6