oj.uz

Submission #289292

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

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 9 ms 7040 KB Output is correct
5 Correct 12 ms 7168 KB Output is correct
6 Correct 23 ms 7296 KB Output is correct
7 Correct 22 ms 7552 KB Output is correct
8 Correct 41 ms 7616 KB Output is correct
9 Correct 40 ms 8572 KB Output is correct
10 Correct 100 ms 9208 KB Output is correct
11 Correct 148 ms 11124 KB Output is correct
12 Correct 163 ms 11764 KB Output is correct
13 Correct 225 ms 11380 KB Output is correct
14 Correct 367 ms 11892 KB Output is correct
15 Correct 326 ms 18664 KB Output is correct

Subtask #2
80.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 2952 ms 24804 KB Output is correct
2 Correct 3759 ms 23140 KB Output is correct
3 Correct 4353 ms 27240 KB Output is correct
4 Correct 320 ms 15080 KB Output is correct
5 Correct 490 ms 17384 KB Output is correct
6 Correct 630 ms 22756 KB Output is correct
7 Correct 2476 ms 23884 KB Output is correct
8 Correct 1906 ms 43348 KB Output is correct
9 Correct 3072 ms 66348 KB Output is correct
10 Execution timed out 8026 ms 73900 KB Time limit exceeded
11 Correct 6036 ms 65716 KB Output is correct
12 Correct 2041 ms 67500 KB Output is correct
13 Correct 2854 ms 68128 KB Output is correct
14 Correct 3838 ms 67800 KB Output is correct
15 Correct 4501 ms 73648 KB Output is correct
16 Correct 3958 ms 82984 KB Output is correct
17 Correct 4641 ms 81068 KB Output is correct