oj.uz

Submission #1100675

# Submission time Handle Problem Language Result Execution time Memory
1100675 2024-10-14T12:39:11 Z not_amir Petrol stations (CEOI24_stations) C++14
18 / 100
 3296 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 = 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(a) == 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);
    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';
}

Compilation message

Main.cpp: In function 'int get_subtree_size(int, int)':
Main.cpp:91:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   91 |     for (auto [u, w] : G[v]) {
      |               ^
Main.cpp: In function 'int get_centroid(int, int, int)':
Main.cpp:99:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   99 |     for (auto [u, w] : G[v]) {
      |               ^
Main.cpp: In function 'void dfs1(SegPoint*, int, int, int, int, int)':
Main.cpp:124:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  124 |     for(auto [u, w] : G[v]) {
      |              ^
Main.cpp: In function 'void dfs2(SegPoint*, int, int, ll, int)':
Main.cpp:154:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  154 |     for(auto [u, w] : G[v]) {
      |              ^
Main.cpp: In function 'void dfs0(int, int, ll)':
Main.cpp:173:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  173 |     for(auto [u, w] : G[v]){
      |              ^
Main.cpp: In function 'void centroid_decomp(int, bool)':
Main.cpp:198:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  198 |     for (auto [u, w] : G[centroid]) {
      |               ^

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 28 ms 18816 KB Output is correct
4 Correct 29 ms 23632 KB Output is correct
5 Correct 20 ms 13304 KB Output is correct
6 Correct 49 ms 29456 KB Output is correct
7 Correct 11 ms 7248 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 29 ms 18776 KB Output is correct
10 Correct 35 ms 19124 KB Output is correct
11 Correct 29 ms 19272 KB Output is correct
12 Correct 28 ms 19036 KB Output is correct
13 Correct 32 ms 18792 KB Output is correct
14 Correct 8 ms 6224 KB Output is correct

Subtask #2
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 588 KB Output is correct
2 Runtime error 3296 ms 2097152 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

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 588 KB Output is correct
4 Runtime error 3296 ms 2097152 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -

Subtask #4
0.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 Runtime error 3116 ms 2097152 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #5
0.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 Runtime error 3116 ms 2097152 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

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 28 ms 18816 KB Output is correct
4 Correct 29 ms 23632 KB Output is correct
5 Correct 20 ms 13304 KB Output is correct
6 Correct 49 ms 29456 KB Output is correct
7 Correct 11 ms 7248 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 29 ms 18776 KB Output is correct
10 Correct 35 ms 19124 KB Output is correct
11 Correct 29 ms 19272 KB Output is correct
12 Correct 28 ms 19036 KB Output is correct
13 Correct 32 ms 18792 KB Output is correct
14 Correct 8 ms 6224 KB Output is correct
15 Correct 1 ms 588 KB Output is correct
16 Runtime error 3296 ms 2097152 KB Execution killed with signal 9
17 Halted 0 ms 0 KB -