oj.uz

Submission #516496

# Submission time Handle Problem Language Result Execution time Memory
516496 2022-01-21T12:21:08 Z blue Regions (IOI09_regions) C++17
30 / 100
 1165 ms 37268 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';
        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 12104 KB Output is correct
2 Correct 6 ms 12104 KB Output is correct
3 Correct 7 ms 12104 KB Output is correct
4 Correct 9 ms 12104 KB Output is correct
5 Correct 12 ms 12104 KB Output is correct
6 Correct 23 ms 12252 KB Output is correct
7 Correct 17 ms 12336 KB Output is correct
8 Correct 31 ms 12360 KB Output is correct
9 Correct 68 ms 12860 KB Output is correct
10 Correct 121 ms 13320 KB Output is correct
11 Correct 136 ms 13892 KB Output is correct
12 Correct 219 ms 14640 KB Output is correct
13 Correct 207 ms 14912 KB Output is correct
14 Correct 209 ms 15840 KB Output is correct
15 Correct 231 ms 17640 KB Output is correct

Subtask #2
15.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 915 ms 21408 KB Output is correct
2 Correct 924 ms 21848 KB Output is correct
3 Correct 1165 ms 23236 KB Output is correct
4 Runtime error 22 ms 26056 KB Execution killed with signal 6
5 Runtime error 22 ms 26684 KB Execution killed with signal 6
6 Runtime error 27 ms 27168 KB Execution killed with signal 6
7 Runtime error 30 ms 28228 KB Execution killed with signal 6
8 Runtime error 38 ms 30816 KB Execution killed with signal 6
9 Runtime error 50 ms 33244 KB Execution killed with signal 6
10 Runtime error 63 ms 35240 KB Execution killed with signal 6
11 Runtime error 78 ms 31924 KB Execution killed with signal 6
12 Runtime error 63 ms 36236 KB Execution killed with signal 6
13 Runtime error 57 ms 35312 KB Execution killed with signal 6
14 Runtime error 61 ms 34956 KB Execution killed with signal 6
15 Runtime error 60 ms 37032 KB Execution killed with signal 6
16 Runtime error 59 ms 37016 KB Execution killed with signal 6
17 Runtime error 69 ms 37268 KB Execution killed with signal 6