oj.uz

Submission #289233

# Submission time Handle Problem Language Result Execution time Memory
289233 2020-09-02T13:29:46 Z PeppaPig Regions (IOI09_regions) C++14
25 / 100
 6169 ms 56876 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;
    assert(ptr <= B);
    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:102:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  102 |         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 5 ms 3712 KB Output is correct
4 Correct 9 ms 3712 KB Output is correct
5 Correct 12 ms 3840 KB Output is correct
6 Correct 29 ms 3968 KB Output is correct
7 Correct 33 ms 4292 KB Output is correct
8 Correct 41 ms 4736 KB Output is correct
9 Correct 68 ms 5380 KB Output is correct
10 Correct 128 ms 10484 KB Output is correct
11 Correct 155 ms 10740 KB Output is correct
12 Correct 204 ms 11512 KB Output is correct
13 Correct 266 ms 16872 KB Output is correct
14 Correct 426 ms 17384 KB Output is correct
15 Correct 516 ms 16888 KB Output is correct

Subtask #2
10.0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 3125 ms 33884 KB Output isn't correct
2 Incorrect 3790 ms 56372 KB Output isn't correct
3 Incorrect 6169 ms 37084 KB Output isn't correct
4 Correct 583 ms 29944 KB Output is correct
5 Correct 804 ms 21228 KB Output is correct
6 Incorrect 838 ms 56364 KB Output isn't correct
7 Incorrect 4946 ms 56876 KB Output isn't correct
8 Incorrect 2747 ms 42292 KB Output isn't correct
9 Runtime error 51 ms 14584 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 51 ms 15480 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 50 ms 12808 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 55 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 51 ms 14280 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Runtime error 51 ms 15480 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Runtime error 56 ms 15480 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Runtime error 57 ms 15352 KB Execution killed with signal 11 (could be triggered by violating memory limits)