oj.uz

Submission #931664

# Submission time Handle Problem Language Result Execution time Memory
931664 2024-02-22T08:32:17 Z LOLOLO Regions (IOI09_regions) C++17
60 / 100
 8000 ms 110132 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

#define           f     first
#define           s     second
#define           pb    push_back
#define           ep    emplace
#define           eb    emplace_back
#define           lb    lower_bound
#define           ub    upper_bound
#define       all(x)    x.begin(), x.end()
#define      rall(x)    x.rbegin(), x.rend()
#define   uniquev(v)    sort(all(v)), (v).resize(unique(all(v)) - (v).begin())
#define     mem(f,x)    memset(f , x , sizeof(f))
#define        sz(x)    (int)(x).size()
#define  __lcm(a, b)    (1ll * ((a) / __gcd((a), (b))) * (b))
#define          mxx    *max_element
#define          mnn    *min_element
#define    cntbit(x)    __builtin_popcountll(x)
#define       len(x)    (int)(x.length())

const int N = 2e5 + 100;
const int lim = 500;

vector <int> lst[N], ed[N], all;
map <int, ll> ans[N], save[N];
int c[N], in[N], ou[N], timer = 1;

void dfs(int u) {
    save[u][c[u]]++;
    in[u] = ++timer;
    for (auto x : ed[u]) {
        dfs(x);
        if (sz(save[u]) < sz(save[x])) {
            swap(save[u], save[x]);
        }

        for (auto t : save[x]) {
            save[u][t.f] += t.s;
        }
    }

    for (auto x : all) {
        if (save[u].find(x) == save[u].end())
            continue;
        ans[c[u]][x] += save[u][x];
    }

    if (sz(lst[c[u]]) >= lim) {
        for (auto x : save[u]) {
            ans[c[u]][x.f] += x.s;
        }
    }

    ou[u] = timer;
}

int f[N];
void upd(int i, int x) {
    for (; i < N; i += i & (-i))
        f[i] += x;
}

int get(int i) {
    int s = 0;
    for (; i; i -= i & (-i))
        s += f[i];

    return s;
}

int range(int l, int r) {
    return get(r) - get(l - 1);
}


int main() {
    int n, r, q;
    cin >> n >> r >> q;
    cin >> c[1];

    for (int i = 2; i <= n; i++) {
        int x;
        cin >> x;
        cin >> c[i];
        ed[x].pb(i);
    }

    for (int i = 1; i <= n; i++) {
        lst[c[i]].pb(i);
    }

    for (int i = 1; i <= r; i++) {
        if (sz(lst[i]) >= lim)
            all.pb(i);
    }

    dfs(1);

    for (int i = 1; i <= q; i++) {
        int r1, r2;
        cin >> r1 >> r2;
        if (max(sz(lst[r1]), sz(lst[r2])) >= lim) {
            cout << ans[r1][r2] << '\n';
        } else {
            int cnt = 0;
            for (auto x : lst[r2])
                upd(in[x], 1);


            for (auto x : lst[r1]) {
                cnt += range(in[x], ou[x]);
            }

            for (auto x : lst[r2])
                upd(in[x], -1);

            cout << cnt << '\n';
        }
    }

    return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 31576 KB Output is correct
2 Correct 6 ms 31576 KB Output is correct
3 Correct 7 ms 31576 KB Output is correct
4 Correct 8 ms 31576 KB Output is correct
5 Correct 11 ms 31576 KB Output is correct
6 Correct 15 ms 31576 KB Output is correct
7 Correct 24 ms 31832 KB Output is correct
8 Correct 25 ms 31832 KB Output is correct
9 Correct 33 ms 32600 KB Output is correct
10 Correct 71 ms 33624 KB Output is correct
11 Correct 96 ms 34384 KB Output is correct
12 Correct 109 ms 34800 KB Output is correct
13 Correct 166 ms 36692 KB Output is correct
14 Correct 253 ms 37644 KB Output is correct
15 Correct 287 ms 41196 KB Output is correct

Subtask #2
45.0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 1166 ms 43116 KB Output isn't correct
2 Incorrect 1158 ms 45496 KB Output isn't correct
3 Incorrect 2319 ms 46576 KB Output isn't correct
4 Correct 260 ms 38464 KB Output is correct
5 Correct 318 ms 39592 KB Output is correct
6 Incorrect 1343 ms 55512 KB Output isn't correct
7 Correct 1662 ms 47820 KB Output is correct
8 Correct 2021 ms 56876 KB Output is correct
9 Correct 2453 ms 61008 KB Output is correct
10 Correct 4296 ms 65984 KB Output is correct
11 Correct 4154 ms 80396 KB Output is correct
12 Correct 2079 ms 71996 KB Output is correct
13 Correct 4996 ms 72276 KB Output is correct
14 Incorrect 6070 ms 110132 KB Output isn't correct
15 Execution timed out 8013 ms 63236 KB Time limit exceeded
16 Execution timed out 8087 ms 83748 KB Time limit exceeded
17 Execution timed out 8071 ms 104612 KB Time limit exceeded