oj.uz

Submission #289238

# Submission time Handle Problem Language Result Execution time Memory
289238 2020-09-02T13:34:47 Z PeppaPig Regions (IOI09_regions) C++14
25 / 100
 8000 ms 131076 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];
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 5 ms 6400 KB Output is correct
2 Correct 5 ms 6400 KB Output is correct
3 Correct 6 ms 6400 KB Output is correct
4 Correct 8 ms 6528 KB Output is correct
5 Correct 13 ms 6656 KB Output is correct
6 Correct 22 ms 6784 KB Output is correct
7 Correct 33 ms 6980 KB Output is correct
8 Correct 40 ms 7424 KB Output is correct
9 Correct 61 ms 8196 KB Output is correct
10 Correct 105 ms 13164 KB Output is correct
11 Correct 168 ms 13428 KB Output is correct
12 Correct 193 ms 14192 KB Output is correct
13 Correct 278 ms 19696 KB Output is correct
14 Correct 351 ms 20200 KB Output is correct
15 Correct 503 ms 19696 KB Output is correct

Subtask #2
10.0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 3118 ms 36576 KB Output isn't correct
2 Incorrect 3536 ms 59060 KB Output isn't correct
3 Incorrect 6082 ms 40044 KB Output isn't correct
4 Correct 639 ms 32584 KB Output is correct
5 Correct 754 ms 23780 KB Output is correct
6 Incorrect 689 ms 59324 KB Output isn't correct
7 Incorrect 4545 ms 59740 KB Output isn't correct
8 Incorrect 3098 ms 45128 KB Output isn't correct
9 Execution timed out 8098 ms 114808 KB Time limit exceeded
10 Execution timed out 8039 ms 126584 KB Time limit exceeded
11 Runtime error 405 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
12 Runtime error 444 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
13 Runtime error 399 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
14 Runtime error 468 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
15 Execution timed out 8064 ms 124084 KB Time limit exceeded
16 Execution timed out 8039 ms 89768 KB Time limit exceeded
17 Execution timed out 8069 ms 86828 KB Time limit exceeded