oj.uz

답안 #1100667

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1100667 2024-10-14T12:29:02 Z crafticat Petrol stations (CEOI24_stations) C++17
8 / 100
 2854 ms 2097152 KB 
#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;
    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, 1e9);
        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) {
        seg->add(x, u);
    }

    int q(int a, int b) {
        return seg->q(a,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 / 0.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 564 KB Output is correct

Subtask #1
0.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 564 KB Output is correct
3 Incorrect 19 ms 14672 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1650 ms 828168 KB Output is correct

Subtask #3
0.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 564 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1650 ms 828168 KB Output is correct
5 Runtime error 2854 ms 2097152 KB Execution killed with signal 9
6 Halted 0 ms 0 KB -

Subtask #4
0.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 564 KB Output is correct
3 Incorrect 1520 ms 757020 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 564 KB Output is correct
3 Incorrect 1520 ms 757020 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0.0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 564 KB Output is correct
3 Incorrect 19 ms 14672 KB Output isn't correct
4 Halted 0 ms 0 KB -