oj.uz

Submission #1100679

# Submission time Handle Problem Language Result Execution time Memory
1100679 2024-10-14T12:42:21 Z not_amir Petrol stations (CEOI24_stations) C++14
55 / 100
 3500 ms 1541200 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';
}

Compilation message

Main.cpp: In function 'int get_subtree_size(int, int)':
Main.cpp:96:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   96 |     for (auto [u, w] : G[v]) {
      |               ^
Main.cpp: In function 'int get_centroid(int, int, int)':
Main.cpp:104:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  104 |     for (auto [u, w] : G[v]) {
      |               ^
Main.cpp: In function 'void dfs1(SegPoint*, int, int, int, int, int)':
Main.cpp:129:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  129 |     for(auto [u, w] : G[v]) {
      |              ^
Main.cpp: In function 'void dfs2(SegPoint*, int, int, ll, int)':
Main.cpp:159:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  159 |     for(auto [u, w] : G[v]) {
      |              ^
Main.cpp: In function 'void dfs0(int, int, ll)':
Main.cpp:178:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  178 |     for(auto [u, w] : G[v]){
      |              ^
Main.cpp: In function 'void centroid_decomp(int, bool)':
Main.cpp:203:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  203 |     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 15 ms 9808 KB Output is correct
4 Correct 9 ms 4604 KB Output is correct
5 Correct 17 ms 9552 KB Output is correct
6 Correct 34 ms 19968 KB Output is correct
7 Correct 4 ms 1104 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 19 ms 12584 KB Output is correct
10 Correct 20 ms 12660 KB Output is correct
11 Correct 21 ms 13392 KB Output is correct
12 Correct 19 ms 13392 KB Output is correct
13 Correct 18 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 1346 ms 486644 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 1346 ms 486644 KB Output is correct
5 Execution timed out 3650 ms 1541200 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 620 ms 185712 KB Output is correct
4 Correct 1604 ms 555916 KB Output is correct
5 Correct 410 ms 52640 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1020 ms 380380 KB Output is correct
8 Correct 1022 ms 380336 KB Output is correct
9 Correct 1018 ms 377764 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 620 ms 185712 KB Output is correct
4 Correct 1604 ms 555916 KB Output is correct
5 Correct 410 ms 52640 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1020 ms 380380 KB Output is correct
8 Correct 1022 ms 380336 KB Output is correct
9 Correct 1018 ms 377764 KB Output is correct
10 Correct 695 ms 352272 KB Output is correct
11 Correct 461 ms 197292 KB Output is correct
12 Correct 397 ms 161012 KB Output is correct
13 Correct 568 ms 222572 KB Output is correct
14 Correct 558 ms 224748 KB Output is correct
15 Correct 586 ms 222640 KB Output is correct
16 Correct 130 ms 65592 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 15 ms 9808 KB Output is correct
4 Correct 9 ms 4604 KB Output is correct
5 Correct 17 ms 9552 KB Output is correct
6 Correct 34 ms 19968 KB Output is correct
7 Correct 4 ms 1104 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 19 ms 12584 KB Output is correct
10 Correct 20 ms 12660 KB Output is correct
11 Correct 21 ms 13392 KB Output is correct
12 Correct 19 ms 13392 KB Output is correct
13 Correct 18 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 1346 ms 486644 KB Output is correct
17 Execution timed out 3650 ms 1541200 KB Time limit exceeded
18 Halted 0 ms 0 KB -