제출 #1100670

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1100670		crafticat	Petrol stations (CEOI24_stations)	C++17	0 / 100	3355 ms	2097152 KiB

Main

#include <bits/stdc++.h>
using namespace std;

template<typename T>
using V = vector<T>;

typedef pair<int, int> pii;
typedef long long ll;

ll INF;

struct Seg {
    Seg *left = nullptr, *right = nullptr;
    int l, r, mid;
    int val = 0;
    bool sparse = false;


    Seg(int l, int r) : l(l), r(r) ,mid((r + l) / 2) {

    }

    void push() {
        if (!sparse) {
            if (r - l > 1 ) {
                left = new Seg(l,mid);
                right = new Seg(mid,r);
            }
            sparse = true;
        }
    }

    void add(int x, int u) {
        push();
        if (r - l <= 1) {
            val += u;
            return;
        }

        if (x < mid)
            left->add(x,u);
        else
            right->add(x,u);
        val = left->val + right->val;
    }

    int q(int a, int b) {
        push();
        if (b <= l || a >= r) return 0;
        if (a <= l && b >= r) return val;

        return left->q(a,b) + right->q(a,b);
    }
};

vector<int> vals;
map<int, int> to;

struct SegPoint {
    Seg *seg;

    SegPoint() {
        seg = new Seg(0, vals.size());
        if (!to.empty()) return;
        std::sort(vals.begin(), vals.end());

        int id = 0;
        for (auto x : vals) {
            to[x] = id++;
        }
    }

    void add(int x, int u) {
        if (to.count(x) == 0) exit(5);
        seg->add(to[x], u);
    }

    int q(int a, int b) {
        if (to.count(a) == 0) exit(5);
        if (to.count(b) == 0) exit(5);
        return seg->q(to[a],to[b]);
    }
};

vector<vector<pii>> G;
vector<bool> is_removed;
vector<int> subsize;

int get_subtree_size(int v, int p = -1) {
    subsize[v] = 1;
    for (auto [u, w] : G[v]) {
        if (u == p || is_removed[u]) { continue; }
        subsize[v] += get_subtree_size(u, v);
    }
    return subsize[v];
}

int get_centroid(int v, int S, int p = -1) {
    for (auto [u, w] : G[v]) {
        if (u == p || is_removed[u]) { continue; }
        if (subsize[u] * 2 > S) {
            return get_centroid(u, S, v);
        }
    }
    return v;
}

int k;

vector<ll> ans, res, jumpw, parw;
vector<int> depth, jump, par;

vector<SegPoint*> st;

void dfs1(SegPoint* stt, int v, int p, int d, int child, int S) {
    depth[v] = d;
    res[v] = 0;
    if(p != -1) {
        if(depth[jump[p]] - depth[p] == depth[jump[jump[p]]] - depth[jump[p]])
            jump[v] = jump[jump[p]], jumpw[v] = jumpw[jump[p]] + jumpw[p] + parw[v];
        else
            jump[v] = p, jumpw[v] = parw[v];
    }
    for(auto [u, w] : G[v]) {
        if(u == p || is_removed[u])
            continue;
        par[u] = v, parw[u] = w;
        if(p == -1)
            st[u] = new SegPoint();
        dfs1(stt, u, v, d + 1, p==-1?u:child, S);
    }

    if (p == -1) return;
    int a = v;
    ll s = 0;
    ans[v] += res[v] * (S - subsize[child]);

    while(jump[a] != a && s + parw[a] <= k) {
        if(jumpw[a] + s <= k)
            s += jumpw[a], a = jump[a];
        else
            s += parw[a], a = par[a];
    }

    if(jump[a] == a) {
        stt->add(k - s, res[v] + 1);
        st[child]->add(k - s, res[v] + 1);
    }
    else
        res[a] += res[v] + 1;
}

void dfs2(SegPoint* stt, int v, int p, ll s, int child) {
    for(auto [u, w] : G[v]) {
        if(u == p || is_removed[u])
            continue;
        if(p == -1) {
            child = u;
        }
        int refuel = stt->q(s, s + w) - st[child]->q(s, s + w);
        ans[v] += refuel * subsize[u];
        stt->add(s + k, refuel);
        dfs2(stt, u, v, s + w, child);
        stt->add(s + k, -refuel);
    }
}

void dfs0(int v, int p, ll s = 0){
    vals.push_back(s);
    for(auto [u, w] : G[v]){
        if(u == p || is_removed[u])
            continue;
        dfs0(u, v, s + w);
    }
}

void centroid_decomp(int v, bool pre) {
    int centroid = get_centroid(v, get_subtree_size(v));

    if(pre) {
        dfs0(centroid, -1);
    }
    else {
        SegPoint *stt = new SegPoint();

        jump[centroid] = centroid;
        jumpw[centroid] = 0;
        dfs1(stt, centroid, -1, 0, 0, get_subtree_size(centroid));
        stt->add( k, 1);
        dfs2(stt, centroid, -1, 0, 0);
    }

    is_removed[centroid] = true;

    for (auto [u, w] : G[centroid]) {
        if (is_removed[u]) { continue; }
        centroid_decomp(u, pre);
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    cin >> n >> k;
    INF = ll(n) * ll(k);
    G.resize(n);
    is_removed.resize(n);
    subsize.resize(n);
    par.resize(n);
    parw.resize(n);
    jump.resize(n);
    jumpw.resize(n);
    ans.resize(n);
    res.resize(n);
    depth.resize(n);
    st.resize(n);
    for(int i = 0; i < n - 1; i++) {
        int u, v, l;
        cin >> u >> v >> l;
        G[u].push_back({v, l});
        G[v].push_back({u, l});
    }
    centroid_decomp(0, 1);
    is_removed.clear();
    is_removed.resize(n);
    centroid_decomp(0, 0);
    for(int i = 0; i < n; i++)
        cout << ans[i] << '\n';
}

• Subtask 0: 0 / 0
• Subtask 1: 0 / 18
• Subtask 2: 0 / 8
• Subtask 3: 0 / 10
• Subtask 4: 0 / 12
• Subtask 5: 0 / 17
• Subtask 6: 0 / 35