oj.uz

Submission #1100694

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

int INF = 0;

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

struct Vertex {
    Vertex* l, * r;
    int 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);
    }
};

int 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<int> vals;
unordered_map<int, int> to;

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;

unordered_map<int, int> cmp;

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) 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) {
        update(stt, 0, INF, cmp[k - s], res[v] + 1);
        update(st[child], 0, INF, cmp[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, cmp[s], cmp[s + w]);
        refuel -= get_sum(st[child], 0, INF, cmp[s], cmp[s + w]);
        ans[v] += refuel * subsize[u];
        update(stt, 0, INF, cmp[s + k], refuel);
        dfs2(stt, u, v, s + w, child);
        update(stt, 0, INF, cmp[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 {
        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, cmp[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;
    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);
    sort(vals.begin(), vals.end());
    for(int x : vals)
        cmp[x] = INF++;
    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:62:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   62 |     for (auto [u, w] : G[v]) {
      |               ^
Main.cpp: In function 'int get_centroid(int, int, int)':
Main.cpp:70:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   70 |     for (auto [u, w] : G[v]) {
      |               ^
Main.cpp: In function 'void dfs1(Vertex*, int, int, int, int, int)':
Main.cpp:97:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   97 |     for(auto [u, w] : G[v]) {
      |              ^
Main.cpp: In function 'void dfs2(Vertex*, int, int, ll, int)':
Main.cpp:127:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  127 |     for(auto [u, w] : G[v]) {
      |              ^
Main.cpp: In function 'void dfs0(int, int, ll)':
Main.cpp:147:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  147 |     for(auto [u, w] : G[v]){
      |              ^
Main.cpp: In function 'void centroid_decomp(int, bool)':
Main.cpp:172:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  172 |     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 12 ms 5968 KB Output is correct
4 Correct 13 ms 6992 KB Output is correct
5 Correct 7 ms 3724 KB Output is correct
6 Correct 16 ms 7504 KB Output is correct
7 Correct 7 ms 2640 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 9 ms 4508 KB Output is correct
10 Correct 9 ms 4688 KB Output is correct
11 Correct 9 ms 4688 KB Output is correct
12 Correct 9 ms 4688 KB Output is correct
13 Correct 9 ms 4860 KB Output is correct
14 Correct 4 ms 2128 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 1556 ms 574936 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 1556 ms 574936 KB Output is correct
5 Execution timed out 3643 ms 1018540 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 1337 ms 522772 KB Output is correct
4 Correct 1825 ms 729680 KB Output is correct
5 Correct 936 ms 225328 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1213 ms 466456 KB Output is correct
8 Correct 1240 ms 467580 KB Output is correct
9 Correct 1161 ms 466640 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 1337 ms 522772 KB Output is correct
4 Correct 1825 ms 729680 KB Output is correct
5 Correct 936 ms 225328 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1213 ms 466456 KB Output is correct
8 Correct 1240 ms 467580 KB Output is correct
9 Correct 1161 ms 466640 KB Output is correct
10 Correct 682 ms 309916 KB Output is correct
11 Correct 830 ms 359564 KB Output is correct
12 Correct 848 ms 331176 KB Output is correct
13 Correct 916 ms 375236 KB Output is correct
14 Correct 912 ms 383088 KB Output is correct
15 Correct 952 ms 383408 KB Output is correct
16 Correct 310 ms 175880 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 12 ms 5968 KB Output is correct
4 Correct 13 ms 6992 KB Output is correct
5 Correct 7 ms 3724 KB Output is correct
6 Correct 16 ms 7504 KB Output is correct
7 Correct 7 ms 2640 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 9 ms 4508 KB Output is correct
10 Correct 9 ms 4688 KB Output is correct
11 Correct 9 ms 4688 KB Output is correct
12 Correct 9 ms 4688 KB Output is correct
13 Correct 9 ms 4860 KB Output is correct
14 Correct 4 ms 2128 KB Output is correct
15 Correct 1 ms 336 KB Output is correct
16 Correct 1556 ms 574936 KB Output is correct
17 Execution timed out 3643 ms 1018540 KB Time limit exceeded
18 Halted 0 ms 0 KB -