oj.uz

Submission #289235

# Submission time Handle Problem Language Result Execution time Memory
289235 2020-09-02T13:31:34 Z PeppaPig Regions (IOI09_regions) C++14
40 / 100
 8000 ms 57048 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 3712 KB Output is correct
2 Correct 3 ms 3712 KB Output is correct
3 Correct 4 ms 3712 KB Output is correct
4 Correct 7 ms 3712 KB Output is correct
5 Correct 9 ms 3840 KB Output is correct
6 Correct 20 ms 3968 KB Output is correct
7 Correct 34 ms 4292 KB Output is correct
8 Correct 24 ms 4736 KB Output is correct
9 Correct 59 ms 5380 KB Output is correct
10 Correct 109 ms 10356 KB Output is correct
11 Correct 161 ms 10732 KB Output is correct
12 Correct 177 ms 11384 KB Output is correct
13 Correct 294 ms 16872 KB Output is correct
14 Correct 425 ms 17384 KB Output is correct
15 Correct 600 ms 16884 KB Output is correct

Subtask #2
25.0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8022 ms 33900 KB Time limit exceeded
2 Execution timed out 8067 ms 56372 KB Time limit exceeded
3 Execution timed out 8042 ms 37232 KB Time limit exceeded
4 Correct 689 ms 29908 KB Output is correct
5 Correct 808 ms 21092 KB Output is correct
6 Correct 3769 ms 56612 KB Output is correct
7 Correct 5912 ms 57048 KB Output is correct
8 Correct 7394 ms 42464 KB Output is correct
9 Runtime error 56 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 51 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 50 ms 14456 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Runtime error 58 ms 14328 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Runtime error 52 ms 15544 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Runtime error 64 ms 15612 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)