oj.uz

Submission #289231

# Submission time Handle Problem Language Result Execution time Memory
289231 2020-09-02T13:28:31 Z PeppaPig Regions (IOI09_regions) C++14
25 / 100
 6236 ms 56948 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 = 1e5 + 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];
int id[M], inv[M], ptr;
long sum[B][B];
vector<int> g[N], emp[M];

int preprocess(int 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;
    return sz;
}

void sack(int u, vector<int> &sub) {
    if(hv[u] != -1) sack(hv[u], sub), ver[u] = ver[hv[u]];
    vector<int> now;
    for(int v : g[u]) if(v != hv[u]) {
        sack(v, now);
        for(int x : now) {
            sub.emplace_back(x);
            ver[u] = update(R[x], 1, ver[u]);
        }
        now = vector<int>();
    }
    sub.emplace_back(u), ver[u] = update(R[u], 1, ver[u]);
    if(id[R[u]]) for(int i = 1; i <= ptr; i++)
        sum[id[R[u]]][i] += get_val(inv[i], ver[u]);
}

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);

    vector<int> tmp;
    preprocess(1), sack(1, tmp);

    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;
            if(!id[a]) {
                ans = 0;
                for(int u : emp[a]) ans += get_val(b, ver[u]);
            } else {
                ans = (long)emp[a].size() * (long)emp[b].size();
                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:85:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   85 |     scanf("%d %d %d %d", &n, &re, &q, R + 1);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
regions.cpp:88:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   88 |         scanf("%d %d", &p, R + i);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~
regions.cpp:101:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  101 |         scanf("%d %d", &a, &b);
      |         ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3616 KB Output is correct
2 Correct 3 ms 3712 KB Output is correct
3 Correct 5 ms 3712 KB Output is correct
4 Correct 7 ms 3712 KB Output is correct
5 Correct 12 ms 3840 KB Output is correct
6 Correct 23 ms 3968 KB Output is correct
7 Correct 32 ms 4292 KB Output is correct
8 Correct 38 ms 4736 KB Output is correct
9 Correct 58 ms 5380 KB Output is correct
10 Correct 117 ms 10356 KB Output is correct
11 Correct 187 ms 10732 KB Output is correct
12 Correct 183 ms 11384 KB Output is correct
13 Correct 334 ms 16864 KB Output is correct
14 Correct 476 ms 17384 KB Output is correct
15 Correct 501 ms 16880 KB Output is correct

Subtask #2
10.0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 3292 ms 34004 KB Output isn't correct
2 Incorrect 3644 ms 56372 KB Output isn't correct
3 Incorrect 6236 ms 37088 KB Output isn't correct
4 Correct 590 ms 29916 KB Output is correct
5 Correct 839 ms 21092 KB Output is correct
6 Incorrect 772 ms 56488 KB Output isn't correct
7 Incorrect 4781 ms 56948 KB Output isn't correct
8 Incorrect 3080 ms 42312 KB Output isn't correct
9 Runtime error 50 ms 14584 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 52 ms 15352 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 56 ms 12792 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 52 ms 14968 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 51 ms 14456 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Runtime error 51 ms 14200 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Runtime error 52 ms 15632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Runtime error 51 ms 15480 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Runtime error 51 ms 15480 KB Execution killed with signal 11 (could be triggered by violating memory limits)