oj.uz

Submission #289295

# Submission time Handle Problem Language Result Execution time Memory
289295 2020-09-02T14:16:37 Z PeppaPig Regions (IOI09_regions) C++14
95 / 100
 8000 ms 82928 KB 
#include <bits/stdc++.h>

#define long long long
#define pii pair<int, int>
#define x first
#define y second

using namespace std;

const int N = 2e5 + 5;
const int M = 2.5e4 + 5;
const int B = 350;

int n, re, q, init;

struct node {
    int d, l, r;
    node(int d, int l, int r) : d(d), l(l), r(r) {}
};

vector<node> vec;

int newleaf(int d) {
    vec.emplace_back(d, -1, -1);
    return (int)vec.size() - 1;
}

int newpar(int l, int r) {
    vec.emplace_back(0, l, r);
    return (int)vec.size() - 1;
}

int build(int l = 1, int r = re) {
    if(l == r) return newleaf(0);
    int mid = (l + r) >> 1;
    return newpar(build(l, mid), build(mid + 1, r));
}

int update(int x, int k, int p, int l = 1, int r = re) {
    if(l == r) return newleaf(vec[p].d + k);
    int mid = (l + r) >> 1;
    if(x <= mid) return newpar(update(x, k, vec[p].l, l, mid), vec[p].r);
    else return newpar(vec[p].l, update(x, k, vec[p].r, mid + 1, r));
}

int get_val(int x, int p, int l = 1, int r = re) {
    if(l == r) return vec[p].d;
    int mid = (l + r) >> 1;
    if(x <= mid) return get_val(x, vec[p].l, l, mid);
    else return get_val(x, vec[p].r, mid + 1, r);
}

int R[N], ver[N], hv[N], in[N], out[N], pos[N];
int id[M], inv[M], cnt[M], ptr;
long sum[B][B];
vector<int> g[N], emp[M], euler[M];

int preprocess(int u) {
    static int idx = 0;

    pos[in[u] = ++idx] = u;
    int sz = 1; pii ret(0, -1);
    for(int v : g[u]) {
        int z = preprocess(v);
        sz += z, ret = max(ret, pii(z, v));
    }
    hv[u] = ret.y, out[u] = idx;
    return sz;
}

void sack(int u, bool save) {
    ver[u] = update(R[u], 1, ver[u]);
    for(int v : g[u]) if(v != hv[u]) {
        ver[v] = ver[u];
        sack(v, 0);
    }
    if(hv[u] != -1) {
        ver[hv[u]] = ver[u];
        sack(hv[u], 1);
    }
    for(int v : g[u]) if(v != hv[u])
        for(int i = in[v]; i <= out[v]; i++)
            ++cnt[R[pos[i]]];
    ++cnt[R[u]];
    if(id[R[u]]) for(int i = 1; i <= ptr; i++)
        sum[id[R[u]]][i] += cnt[inv[i]];
    if(!save) for(int i = in[u]; i <= out[u]; i++)
        --cnt[R[pos[i]]];
}

int main() {
    scanf("%d %d %d %d", &n, &re, &q, R + 1);
    emp[R[1]].emplace_back(1);
    for(int i = 2, p; i <= n; i++) {
        scanf("%d %d", &p, R + i);
        g[p].emplace_back(i);
        emp[R[i]].emplace_back(i);
    }
    for(int i = 1; i <= re; i++) if((int)emp[i].size() >= B)
        inv[id[i] = ++ptr] = i;
    init = build();
    fill_n(ver, N, init);

    preprocess(1), sack(1, 1);
    for(int i = 1; i <= n; i++) euler[R[pos[i]]].emplace_back(i);

    for(int i = 1, a, b; i <= q; i++) {
        scanf("%d %d", &a, &b);
        if(id[a] && id[b]) printf("%lld\n", sum[id[a]][id[b]]);
        else {
            long ans = 0;
            if(!id[a])
                for(int u : emp[a])
                    ans += upper_bound(euler[b].begin(), euler[b].end(), out[u])
                        - lower_bound(euler[b].begin(), euler[b].end(), in[u]);
            else for(int u : emp[b]) ans += get_val(a, ver[u]);
            printf("%lld\n", ans);
        }
        fflush(stdout);
    }

    return 0;
}

Compilation message

regions.cpp: In function 'int main()':
regions.cpp:92:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   92 |     scanf("%d %d %d %d", &n, &re, &q, R + 1);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
regions.cpp:95:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   95 |         scanf("%d %d", &p, R + i);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~
regions.cpp:108:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  108 |         scanf("%d %d", &a, &b);
      |         ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7040 KB Output is correct
2 Correct 5 ms 7040 KB Output is correct
3 Correct 7 ms 7040 KB Output is correct
4 Correct 9 ms 7040 KB Output is correct
5 Correct 11 ms 7168 KB Output is correct
6 Correct 24 ms 7420 KB Output is correct
7 Correct 35 ms 7424 KB Output is correct
8 Correct 36 ms 7616 KB Output is correct
9 Correct 57 ms 8572 KB Output is correct
10 Correct 98 ms 9208 KB Output is correct
11 Correct 156 ms 11124 KB Output is correct
12 Correct 175 ms 11764 KB Output is correct
13 Correct 222 ms 11244 KB Output is correct
14 Correct 380 ms 11884 KB Output is correct
15 Correct 332 ms 18668 KB Output is correct

Subtask #2
80.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 2870 ms 24804 KB Output is correct
2 Correct 3646 ms 23268 KB Output is correct
3 Correct 4229 ms 27364 KB Output is correct
4 Correct 287 ms 14952 KB Output is correct
5 Correct 375 ms 17392 KB Output is correct
6 Correct 547 ms 22756 KB Output is correct
7 Correct 2270 ms 23892 KB Output is correct
8 Correct 1704 ms 43224 KB Output is correct
9 Correct 2999 ms 66392 KB Output is correct
10 Execution timed out 8022 ms 73944 KB Time limit exceeded
11 Correct 6205 ms 65712 KB Output is correct
12 Correct 2425 ms 67500 KB Output is correct
13 Correct 2992 ms 68268 KB Output is correct
14 Correct 3612 ms 67636 KB Output is correct
15 Correct 4787 ms 73800 KB Output is correct
16 Correct 4193 ms 82928 KB Output is correct
17 Correct 4683 ms 81068 KB Output is correct