oj.uz

Submission #1100678

# Submission time Handle Problem Language Result Execution time Memory
1100678 2024-10-14T12:42:03 Z crafticat Petrol stations (CEOI24_stations) C++17
55 / 100
 3500 ms 1343896 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 = 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() {
        static int id = 0;
        
        if (!to.empty()) {
            seg = new Seg(0, id);
            return;
        }
        std::sort(vals.begin(), vals.end());

        int last = -1;
        for (auto x : vals) {
            if (last == x) continue;
            to[x] = id++;
            last = x;
        }
        
        seg = new Seg(0, id);
    }

    void add(int x, int u) {
        seg->add(to[x], u);
    }

    int q(int a, int b) {
        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);
    vals.push_back(s + k);
    if(k - s > 0)
        vals.push_back(k - 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

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct

Subtask #1
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 14 ms 9808 KB Output is correct
4 Correct 8 ms 4688 KB Output is correct
5 Correct 14 ms 9452 KB Output is correct
6 Correct 32 ms 19968 KB Output is correct
7 Correct 3 ms 1104 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 18 ms 12624 KB Output is correct
10 Correct 18 ms 12624 KB Output is correct
11 Correct 19 ms 13392 KB Output is correct
12 Correct 19 ms 13392 KB Output is correct
13 Correct 19 ms 12880 KB Output is correct
14 Correct 5 ms 3920 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1382 ms 486724 KB Output is correct

Subtask #3
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1382 ms 486724 KB Output is correct
5 Execution timed out 3659 ms 1343896 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 609 ms 185520 KB Output is correct
4 Correct 1628 ms 555972 KB Output is correct
5 Correct 407 ms 52640 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 981 ms 380328 KB Output is correct
8 Correct 986 ms 380312 KB Output is correct
9 Correct 994 ms 377780 KB Output is correct

Subtask #5
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 609 ms 185520 KB Output is correct
4 Correct 1628 ms 555972 KB Output is correct
5 Correct 407 ms 52640 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 981 ms 380328 KB Output is correct
8 Correct 986 ms 380312 KB Output is correct
9 Correct 994 ms 377780 KB Output is correct
10 Correct 744 ms 352576 KB Output is correct
11 Correct 494 ms 197296 KB Output is correct
12 Correct 456 ms 161032 KB Output is correct
13 Correct 578 ms 222588 KB Output is correct
14 Correct 595 ms 224684 KB Output is correct
15 Correct 594 ms 222620 KB Output is correct
16 Correct 124 ms 65676 KB Output is correct

Subtask #6
0.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 14 ms 9808 KB Output is correct
4 Correct 8 ms 4688 KB Output is correct
5 Correct 14 ms 9452 KB Output is correct
6 Correct 32 ms 19968 KB Output is correct
7 Correct 3 ms 1104 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 18 ms 12624 KB Output is correct
10 Correct 18 ms 12624 KB Output is correct
11 Correct 19 ms 13392 KB Output is correct
12 Correct 19 ms 13392 KB Output is correct
13 Correct 19 ms 12880 KB Output is correct
14 Correct 5 ms 3920 KB Output is correct
15 Correct 1 ms 336 KB Output is correct
16 Correct 1382 ms 486724 KB Output is correct
17 Execution timed out 3659 ms 1343896 KB Time limit exceeded
18 Halted 0 ms 0 KB -