oj.uz

Submission #516495

# Submission time Handle Problem Language Result Execution time Memory
516495 2022-01-21T12:20:55 Z blue Regions (IOI09_regions) C++17
30 / 100
 1353 ms 37080 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';
        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 5 ms 12196 KB Output is correct
2 Correct 5 ms 12104 KB Output is correct
3 Correct 7 ms 12104 KB Output is correct
4 Correct 10 ms 12104 KB Output is correct
5 Correct 14 ms 12104 KB Output is correct
6 Correct 24 ms 12232 KB Output is correct
7 Correct 30 ms 12312 KB Output is correct
8 Correct 45 ms 12360 KB Output is correct
9 Correct 64 ms 12744 KB Output is correct
10 Correct 126 ms 13448 KB Output is correct
11 Correct 139 ms 13888 KB Output is correct
12 Correct 206 ms 14644 KB Output is correct
13 Correct 244 ms 15044 KB Output is correct
14 Correct 172 ms 15848 KB Output is correct
15 Correct 228 ms 17716 KB Output is correct

Subtask #2
15.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 715 ms 21408 KB Output is correct
2 Correct 917 ms 21836 KB Output is correct
3 Correct 1353 ms 23360 KB Output is correct
4 Runtime error 23 ms 26060 KB Execution killed with signal 6
5 Runtime error 24 ms 26756 KB Execution killed with signal 6
6 Runtime error 28 ms 27120 KB Execution killed with signal 6
7 Runtime error 32 ms 28212 KB Execution killed with signal 6
8 Runtime error 41 ms 30772 KB Execution killed with signal 6
9 Runtime error 53 ms 33356 KB Execution killed with signal 6
10 Runtime error 71 ms 35324 KB Execution killed with signal 6
11 Runtime error 60 ms 31724 KB Execution killed with signal 6
12 Runtime error 58 ms 36296 KB Execution killed with signal 6
13 Runtime error 65 ms 35248 KB Execution killed with signal 6
14 Runtime error 79 ms 34948 KB Execution killed with signal 6
15 Runtime error 70 ms 37004 KB Execution killed with signal 6
16 Runtime error 59 ms 37080 KB Execution killed with signal 6
17 Runtime error 58 ms 37048 KB Execution killed with signal 6