oj.uz

Submission #1100650

# Submission time Handle Problem Language Result Execution time Memory
1100650 2024-10-14T11:39:53 Z not_amir Petrol stations (CEOI24_stations) C++14
55 / 100
 3500 ms 2040096 KB 
#include <bits/stdc++.h>
using namespace std;

#pragma GCC optimize("O3")

typedef pair<int, int> pii;
typedef long long ll;

#define INF 1e15

struct Vertex {
    Vertex* l, * r;
    ll sum;

    Vertex(ll val) : l(nullptr), r(nullptr), sum(val) {}
    Vertex(Vertex* l, Vertex* r) : l(l), r(r), sum(0) {
        if (l) sum += l->sum;
        if (r) sum += r->sum;
    }

    void extend(){
        if(!l)
            l = new Vertex(0);
        if(!r)
            r = new Vertex(0);
    }
};

ll get_sum(Vertex* v, ll tl, ll tr, ll l, ll r) {
    if (l + 1 > r)
        return 0;
    if (l == tl && tr == r)
        return v->sum;
    if(v->l == nullptr)
        return 0;
    ll tm = (tl + tr) / 2;
    return get_sum(v->l, tl, tm, l, min(r, tm))
        + get_sum(v->r, tm, tr, max(l, tm), r);
}

void update(Vertex* v, ll tl, ll tr, ll pos, int new_val) {
    if (tl + 1 == tr){
        v->sum += new_val;
        return;
    }
    v->extend();
    ll tm = (tl + tr) / 2;
    if (pos < tm)
        update(v->l, tl, tm, pos, new_val);
    else
        update(v->r, tm, tr, pos, new_val);
    v->sum = v->l->sum + v->r->sum;
}

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<Vertex*> st;

void dfs1(Vertex* 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 Vertex(0);
        dfs1(stt, u, v, d + 1, p==-1?u:child, S);
    }
    if(p != -1) {
        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) {
            update(stt, 0, INF, k - s, res[v] + 1);
            update(st[child], 0, INF, k - s, res[v] + 1);
        }
        else
            res[a] += res[v] + 1;
    }
}

void dfs2(Vertex* 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 = get_sum(stt, 0, INF, s, s + w);
        refuel -= get_sum(st[child], 0, INF, s, s + w);
        ans[v] += refuel * subsize[u];
        update(stt, 0, INF, s + k, refuel);
        dfs2(stt, u, v, s + w, child);
        update(stt, 0, INF, s + k, -refuel);
    }
}

void centroid_decomp(int v = 0) {
    int centroid = get_centroid(v, get_subtree_size(v));

    Vertex* stt = new Vertex(0);

    jump[centroid] = centroid;
    jumpw[centroid] = 0;
    dfs1(stt, centroid, -1, 0, 0, get_subtree_size(centroid));
    update(stt, 0, INF, 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);
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    cin >> n >> 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();
    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:61:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   61 |     for (auto [u, w] : G[v]) {
      |               ^
Main.cpp: In function 'int get_centroid(int, int, int)':
Main.cpp:69:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   69 |     for (auto [u, w] : G[v]) {
      |               ^
Main.cpp: In function 'void dfs1(Vertex*, int, int, int, int, int)':
Main.cpp:94:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   94 |     for(auto [u, w] : G[v]) {
      |              ^
Main.cpp: In function 'void dfs2(Vertex*, int, int, ll, int)':
Main.cpp:122:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  122 |     for(auto [u, w] : G[v]) {
      |              ^
Main.cpp: In function 'void centroid_decomp(int)':
Main.cpp:149:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  149 |     for (auto [u, w] : G[centroid]) {
      |               ^

Subtask #0
0.0 / 0.0

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

Subtask #1
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 19 ms 7508 KB Output is correct
4 Correct 25 ms 7156 KB Output is correct
5 Correct 14 ms 8020 KB Output is correct
6 Correct 21 ms 10836 KB Output is correct
7 Correct 17 ms 6888 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 16 ms 8276 KB Output is correct
10 Correct 16 ms 8532 KB Output is correct
11 Correct 16 ms 8440 KB Output is correct
12 Correct 16 ms 8420 KB Output is correct
13 Correct 16 ms 8276 KB Output is correct
14 Correct 10 ms 6740 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1562 ms 481820 KB Output is correct

Subtask #3
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1562 ms 481820 KB Output is correct
5 Execution timed out 3702 ms 2040096 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 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1380 ms 468308 KB Output is correct
4 Correct 1685 ms 511316 KB Output is correct
5 Correct 1473 ms 457808 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1354 ms 481132 KB Output is correct
8 Correct 1388 ms 481120 KB Output is correct
9 Correct 1368 ms 481164 KB Output is correct

Subtask #5
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1380 ms 468308 KB Output is correct
4 Correct 1685 ms 511316 KB Output is correct
5 Correct 1473 ms 457808 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1354 ms 481132 KB Output is correct
8 Correct 1388 ms 481120 KB Output is correct
9 Correct 1368 ms 481164 KB Output is correct
10 Correct 912 ms 462944 KB Output is correct
11 Correct 999 ms 461644 KB Output is correct
12 Correct 1089 ms 459072 KB Output is correct
13 Correct 1153 ms 469868 KB Output is correct
14 Correct 1159 ms 469768 KB Output is correct
15 Correct 1161 ms 469972 KB Output is correct
16 Correct 696 ms 451008 KB Output is correct

Subtask #6
0.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 19 ms 7508 KB Output is correct
4 Correct 25 ms 7156 KB Output is correct
5 Correct 14 ms 8020 KB Output is correct
6 Correct 21 ms 10836 KB Output is correct
7 Correct 17 ms 6888 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 16 ms 8276 KB Output is correct
10 Correct 16 ms 8532 KB Output is correct
11 Correct 16 ms 8440 KB Output is correct
12 Correct 16 ms 8420 KB Output is correct
13 Correct 16 ms 8276 KB Output is correct
14 Correct 10 ms 6740 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1562 ms 481820 KB Output is correct
17 Execution timed out 3702 ms 2040096 KB Time limit exceeded
18 Halted 0 ms 0 KB -