Submission #289235

#	Time	Username	Problem	Language	Result	Execution time	Memory
289235		PeppaPig	Regions (IOI09_regions)	C++14	40 / 100	8067 ms	57048 KiB

regions

#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 (stderr)

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 / 15
• Subtask 2: 25 / 85