oj.uz

Submission #1100701

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

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

constexpr int N = 7e4;

ll INF;

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<pii> G[N];
bool is_removed[N];
int subsize[N];

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;

ll ans[N], res[N], jumpw[N], parw[N];
int depth[N], jump[N], par[N];

Vertex* st[N];

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) {
    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() {
    srand(time(nullptr));
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    cin >> n >> k;
    INF = ll(n) * ll(k);
    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(rand() % n);
    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 2 ms 5712 KB Output is correct
2 Correct 2 ms 5712 KB Output is correct

Subtask #1
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5712 KB Output is correct
2 Correct 2 ms 5712 KB Output is correct
3 Correct 12 ms 9820 KB Output is correct
4 Correct 9 ms 8784 KB Output is correct
5 Correct 9 ms 9544 KB Output is correct
6 Correct 15 ms 12112 KB Output is correct
7 Correct 8 ms 8272 KB Output is correct
8 Correct 2 ms 5712 KB Output is correct
9 Correct 10 ms 9872 KB Output is correct
10 Correct 10 ms 10076 KB Output is correct
11 Correct 10 ms 10232 KB Output is correct
12 Correct 10 ms 10076 KB Output is correct
13 Correct 10 ms 10064 KB Output is correct
14 Correct 6 ms 8272 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5880 KB Output is correct
2 Correct 708 ms 185836 KB Output is correct

Subtask #3
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5712 KB Output is correct
2 Correct 2 ms 5712 KB Output is correct
3 Correct 2 ms 5880 KB Output is correct
4 Correct 708 ms 185836 KB Output is correct
5 Execution timed out 3707 ms 2097152 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5712 KB Output is correct
2 Correct 2 ms 5712 KB Output is correct
3 Correct 631 ms 188624 KB Output is correct
4 Correct 809 ms 233644 KB Output is correct
5 Correct 656 ms 183112 KB Output is correct
6 Correct 2 ms 5712 KB Output is correct
7 Correct 587 ms 211996 KB Output is correct
8 Correct 618 ms 212040 KB Output is correct
9 Correct 591 ms 212248 KB Output is correct

Subtask #5
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5712 KB Output is correct
2 Correct 2 ms 5712 KB Output is correct
3 Correct 631 ms 188624 KB Output is correct
4 Correct 809 ms 233644 KB Output is correct
5 Correct 656 ms 183112 KB Output is correct
6 Correct 2 ms 5712 KB Output is correct
7 Correct 587 ms 211996 KB Output is correct
8 Correct 618 ms 212040 KB Output is correct
9 Correct 591 ms 212248 KB Output is correct
10 Correct 409 ms 190280 KB Output is correct
11 Correct 452 ms 188960 KB Output is correct
12 Correct 453 ms 179808 KB Output is correct
13 Correct 506 ms 200776 KB Output is correct
14 Correct 520 ms 200776 KB Output is correct
15 Correct 531 ms 200644 KB Output is correct
16 Correct 247 ms 165052 KB Output is correct

Subtask #6
0.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5712 KB Output is correct
2 Correct 2 ms 5712 KB Output is correct
3 Correct 12 ms 9820 KB Output is correct
4 Correct 9 ms 8784 KB Output is correct
5 Correct 9 ms 9544 KB Output is correct
6 Correct 15 ms 12112 KB Output is correct
7 Correct 8 ms 8272 KB Output is correct
8 Correct 2 ms 5712 KB Output is correct
9 Correct 10 ms 9872 KB Output is correct
10 Correct 10 ms 10076 KB Output is correct
11 Correct 10 ms 10232 KB Output is correct
12 Correct 10 ms 10076 KB Output is correct
13 Correct 10 ms 10064 KB Output is correct
14 Correct 6 ms 8272 KB Output is correct
15 Correct 2 ms 5880 KB Output is correct
16 Correct 708 ms 185836 KB Output is correct
17 Execution timed out 3707 ms 2097152 KB Time limit exceeded
18 Halted 0 ms 0 KB -