oj.uz

Submission #931678

# Submission time Handle Problem Language Result Execution time Memory
931678 2024-02-22T08:53:29 Z LOLOLO Regions (IOI09_regions) C++17
100 / 100
 3360 ms 72708 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, e[N];
map <int, int> ans[N];
int c[N], in[N], ou[N], timer = 1, cnt[N];

void dfs(int u) {
    cnt[c[u]]++;
    in[u] = ++timer;

    for (auto x : ed[u]) {
        dfs(x);
    }

    cnt[c[u]]--;
    for (auto x : all) {
        ans[x][c[u]] += cnt[x];
    }

    ou[u] = timer;
}

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 <= n; i++) {
        e[c[i]].pb(in[i]);
    }

    for (int i = 1; i <= r; i++) {
        sort(all(e[i]));
    }

    for (int i = 1; i <= q; i++) {
        int r1, r2;
        cin >> r1 >> r2;
        if (sz(lst[r1]) >= lim) {
            cout << ans[r1][r2] << '\n';
        } else {
            int cnt = 0;
            for (auto x : lst[r1]) {
                int l = lower_bound(all(e[r2]), in[x]) - e[r2].begin(), r = upper_bound(all(e[r2]), ou[x]) - e[r2].begin() - 1;
                cnt += (r - l + 1);
            }

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

    return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 26712 KB Output is correct
2 Correct 6 ms 26712 KB Output is correct
3 Correct 7 ms 26712 KB Output is correct
4 Correct 9 ms 26712 KB Output is correct
5 Correct 10 ms 26712 KB Output is correct
6 Correct 18 ms 26968 KB Output is correct
7 Correct 25 ms 26712 KB Output is correct
8 Correct 21 ms 26968 KB Output is correct
9 Correct 31 ms 27480 KB Output is correct
10 Correct 57 ms 27224 KB Output is correct
11 Correct 77 ms 27464 KB Output is correct
12 Correct 96 ms 28088 KB Output is correct
13 Correct 152 ms 27576 KB Output is correct
14 Correct 212 ms 27956 KB Output is correct
15 Correct 228 ms 32836 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1427 ms 31652 KB Output is correct
2 Correct 1687 ms 29568 KB Output is correct
3 Correct 2261 ms 34344 KB Output is correct
4 Correct 176 ms 28180 KB Output is correct
5 Correct 265 ms 31168 KB Output is correct
6 Correct 852 ms 34752 KB Output is correct
7 Correct 1281 ms 30456 KB Output is correct
8 Correct 1032 ms 40156 KB Output is correct
9 Correct 1701 ms 35636 KB Output is correct
10 Correct 3360 ms 44720 KB Output is correct
11 Correct 3268 ms 34184 KB Output is correct
12 Correct 1054 ms 37036 KB Output is correct
13 Correct 1479 ms 37872 KB Output is correct
14 Correct 1784 ms 53696 KB Output is correct
15 Correct 2575 ms 46404 KB Output is correct
16 Correct 2141 ms 59112 KB Output is correct
17 Correct 2421 ms 72708 KB Output is correct