Submission #1313954

#	Time	Username	Problem	Language	Result	Execution time	Memory
1313954		nicolo_010	트리 (IOI24_tree)	C++20	0 / 100	2096 ms	33652 KiB

tree

#include <bits/stdc++.h>
#include "tree.h"
using namespace std;
using ll = long long;
using pii = pair<int, int>;

int n;
std::vector<int> p, w;

struct SegTree {
    vector<int> tree;
    void init() {
        tree.assign(4*n, 0);
    }
    void query(int p, int l, int r, int i, int x) {
        if (l>i || r<i) return;
        if (l==r) {
            tree[p] = x;
            return;
        }
        int m = (l+r)/2;
        query(2*p, l, m, i, x);
        query(2*p+1, m+1, r, i, x);
        int i1 = tree[2*p];
        int i2 = tree[2*p+1];
        if (i1==-1) {
            tree[p] = i2;
            return;
        }
        if (i2==-1) {
            tree[p] = i1;
            return;
        }
        if (w[i1] < w[i2]) tree[p] = i1;
        else tree[p] = i2;
    }

    int rmq(int p, int l, int r, int i, int j) {
        if (l > j || r < i) return -1;
        if (i <= l && r <= j) {
            return tree[p];
        }
        int m = (l+r)/2;
        int i1 = rmq(2*p, l, m, i, j);
        int i2 = rmq(2*p+1, m+1, r, i, j);
        if (i1==-1) return i2;
        if (i2==-1) return i1;
        if (w[i1] < w[i2]) return i1;
        else return i2;
    }
};

SegTree st;
vector<vector<int>> adj;
vector<int> leaf;
vector<int> in, out;
vector<bool> isleaf;
int t;

void dfs(int u, int p=-1) {
    bool can = true;
    in[u] = t++;
    for (auto x : adj[u]) {
        if (x==p) continue;
        dfs(x, u);
        can = false;
    }
    out[u] = t;
    if (can) {
        leaf.push_back(u);
        isleaf[u] = true;
    }
}

void init(std::vector<int> P, std::vector<int> W) {
    p = P;
    w = W;
    n = (int)p.size();
    adj.assign(n, {});
    in.assign(n, 0);
    out.assign(n, 0);
    isleaf.assign(n, false);
    t=0;
    for (int i=1; i<n; i++) {
        int a = i;
        int b = p[i];
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    t=0;
    dfs(0);
}

long long query(int L, int R) {
    vector<ll> c(n, 0);
    vector<ll> S(n, 0);
    st.init();
    for (int i=0; i<n; i++) {
        if (!isleaf[i]) st.query(1, 0, n-1, in[i], i);
        else st.query(1, 0, n-1, in[i], -1);
    }
    for (int i=n-1; i>=0; i--) {
        if (isleaf[i]) {
            c[i] = L;
            S[i] = L;
        }
        else {
            while (S[i] > R) {
                int idx = st.rmq(1, 0, n-1, in[i], out[i]-1);
                S[idx]--;
                S[i]--;
                c[idx]--;
                if (S[idx] == L) st.query(1, 0, n-1, in[idx], -1);
            }
            if (S[i] == L) st.query(1, 0, n-1, in[i], -1);
        }
        if (i==0) continue;
        S[p[i]] += S[i];
    }
    ll ans=0;
    for (int i=0; i<n; i++) {
        ans += abs(c[i])*w[i];
    }
    return ans;
}

• Subtask 0: 0 / 0
• Subtask 1: 0 / 10
• Subtask 2: 0 / 13
• Subtask 3: 0 / 18
• Subtask 4: 0 / 7
• Subtask 5: 0 / 11
• Subtask 6: 0 / 22
• Subtask 7: 0 / 19