oj.uz

Submission #289287

# Submission time Handle Problem Language Result Execution time Memory
289287 2020-09-02T14:12:14 Z PeppaPig Regions (IOI09_regions) C++14
95 / 100
 8000 ms 82980 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 = 450;

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 6 ms 7040 KB Output is correct
4 Correct 10 ms 7040 KB Output is correct
5 Correct 13 ms 7168 KB Output is correct
6 Correct 26 ms 7416 KB Output is correct
7 Correct 44 ms 7424 KB Output is correct
8 Correct 50 ms 7616 KB Output is correct
9 Correct 69 ms 8572 KB Output is correct
10 Correct 90 ms 9208 KB Output is correct
11 Correct 147 ms 11124 KB Output is correct
12 Correct 199 ms 11764 KB Output is correct
13 Correct 249 ms 11252 KB Output is correct
14 Correct 427 ms 11892 KB Output is correct
15 Correct 404 ms 18672 KB Output is correct

Subtask #2
80.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 3302 ms 24804 KB Output is correct
2 Correct 3935 ms 23156 KB Output is correct
3 Correct 4440 ms 27236 KB Output is correct
4 Correct 387 ms 14960 KB Output is correct
5 Correct 369 ms 17392 KB Output is correct
6 Correct 588 ms 22884 KB Output is correct
7 Correct 1916 ms 23892 KB Output is correct
8 Correct 1897 ms 43348 KB Output is correct
9 Correct 2991 ms 66348 KB Output is correct
10 Execution timed out 8051 ms 73772 KB Time limit exceeded
11 Correct 6797 ms 65748 KB Output is correct
12 Correct 2164 ms 67500 KB Output is correct
13 Correct 3172 ms 68188 KB Output is correct
14 Correct 4046 ms 67760 KB Output is correct
15 Correct 4907 ms 73652 KB Output is correct
16 Correct 4035 ms 82980 KB Output is correct
17 Correct 4534 ms 81068 KB Output is correct