oj.uz

Submission #931676

# Submission time Handle Problem Language Result Execution time Memory
931676 2024-02-22T08:50:45 Z LOLOLO Regions (IOI09_regions) C++17
45 / 100
 3418 ms 70260 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]]++;
    }

    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 26804 KB Output is correct
3 Correct 8 ms 26712 KB Output is correct
4 Correct 8 ms 26712 KB Output is correct
5 Correct 9 ms 26712 KB Output is correct
6 Correct 15 ms 26968 KB Output is correct
7 Correct 19 ms 26712 KB Output is correct
8 Correct 21 ms 26968 KB Output is correct
9 Correct 40 ms 27732 KB Output is correct
10 Correct 56 ms 27224 KB Output is correct
11 Correct 85 ms 27360 KB Output is correct
12 Correct 98 ms 28136 KB Output is correct
13 Correct 125 ms 27612 KB Output is correct
14 Correct 199 ms 27956 KB Output is correct
15 Correct 209 ms 32316 KB Output is correct

Subtask #2
30.0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 1402 ms 31428 KB Output isn't correct
2 Incorrect 1600 ms 29432 KB Output isn't correct
3 Incorrect 2131 ms 33992 KB Output isn't correct
4 Correct 170 ms 28288 KB Output is correct
5 Correct 218 ms 30716 KB Output is correct
6 Incorrect 863 ms 34804 KB Output isn't correct
7 Correct 1257 ms 30064 KB Output is correct
8 Incorrect 1051 ms 39196 KB Output isn't correct
9 Correct 1693 ms 35596 KB Output is correct
10 Correct 3418 ms 43304 KB Output is correct
11 Correct 3318 ms 33908 KB Output is correct
12 Incorrect 1018 ms 36856 KB Output isn't correct
13 Incorrect 1463 ms 37728 KB Output isn't correct
14 Incorrect 1788 ms 53320 KB Output isn't correct
15 Incorrect 2357 ms 45328 KB Output isn't correct
16 Incorrect 2206 ms 56088 KB Output isn't correct
17 Incorrect 2427 ms 70260 KB Output isn't correct