oj.uz

Submission #1100680

# Submission time Handle Problem Language Result Execution time Memory
1100680 2024-10-14T12:42:42 Z crafticat Petrol stations (CEOI24_stations) C++17
55 / 100
 3500 ms 1924500 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;
unordered_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 13 ms 9768 KB Output is correct
4 Correct 8 ms 4688 KB Output is correct
5 Correct 14 ms 9552 KB Output is correct
6 Correct 29 ms 19792 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 12636 KB Output is correct
10 Correct 18 ms 12796 KB Output is correct
11 Correct 18 ms 13544 KB Output is correct
12 Correct 19 ms 13196 KB Output is correct
13 Correct 19 ms 12880 KB Output is correct
14 Correct 6 ms 3920 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 504 KB Output is correct
2 Correct 1202 ms 486648 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 504 KB Output is correct
4 Correct 1202 ms 486648 KB Output is correct
5 Execution timed out 3673 ms 1924500 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 711 ms 185904 KB Output is correct
4 Correct 1440 ms 555636 KB Output is correct
5 Correct 479 ms 52640 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 933 ms 380188 KB Output is correct
8 Correct 978 ms 380296 KB Output is correct
9 Correct 927 ms 377904 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 711 ms 185904 KB Output is correct
4 Correct 1440 ms 555636 KB Output is correct
5 Correct 479 ms 52640 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 933 ms 380188 KB Output is correct
8 Correct 978 ms 380296 KB Output is correct
9 Correct 927 ms 377904 KB Output is correct
10 Correct 667 ms 352168 KB Output is correct
11 Correct 481 ms 197296 KB Output is correct
12 Correct 452 ms 161192 KB Output is correct
13 Correct 530 ms 222396 KB Output is correct
14 Correct 483 ms 224684 KB Output is correct
15 Correct 487 ms 222696 KB Output is correct
16 Correct 102 ms 65668 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 13 ms 9768 KB Output is correct
4 Correct 8 ms 4688 KB Output is correct
5 Correct 14 ms 9552 KB Output is correct
6 Correct 29 ms 19792 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 12636 KB Output is correct
10 Correct 18 ms 12796 KB Output is correct
11 Correct 18 ms 13544 KB Output is correct
12 Correct 19 ms 13196 KB Output is correct
13 Correct 19 ms 12880 KB Output is correct
14 Correct 6 ms 3920 KB Output is correct
15 Correct 1 ms 504 KB Output is correct
16 Correct 1202 ms 486648 KB Output is correct
17 Execution timed out 3673 ms 1924500 KB Time limit exceeded
18 Halted 0 ms 0 KB -