oj.uz

답안 #1100659

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1100659 2024-10-14T11:52:34 Z not_amir Petrol stations (CEOI24_stations) C++14
55 / 100
 3500 ms 2037904 KB 
#include <bits/stdc++.h>
using namespace std;

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

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<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;
    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();
    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:59:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   59 |     for (auto [u, w] : G[v]) {
      |               ^
Main.cpp: In function 'int get_centroid(int, int, int)':
Main.cpp:67:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   67 |     for (auto [u, w] : G[v]) {
      |               ^
Main.cpp: In function 'void dfs1(Vertex*, int, int, int, int, int)':
Main.cpp:92:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   92 |     for(auto [u, w] : G[v]) {
      |              ^
Main.cpp: In function 'void dfs2(Vertex*, int, int, ll, int)':
Main.cpp:120:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  120 |     for(auto [u, w] : G[v]) {
      |              ^
Main.cpp: In function 'void centroid_decomp(int)':
Main.cpp:147:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  147 |     for (auto [u, w] : G[centroid]) {
      |               ^

Subtask #0
0.0 / 0.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 0 ms 336 KB Output is correct

Subtask #1
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 0 ms 336 KB Output is correct
3 Correct 8 ms 4688 KB Output is correct
4 Correct 7 ms 3408 KB Output is correct
5 Correct 9 ms 4176 KB Output is correct
6 Correct 12 ms 6852 KB Output is correct
7 Correct 7 ms 2896 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 8 ms 4688 KB Output is correct
10 Correct 8 ms 4704 KB Output is correct
11 Correct 8 ms 4688 KB Output is correct
12 Correct 8 ms 4688 KB Output is correct
13 Correct 9 ms 4688 KB Output is correct
14 Correct 4 ms 3152 KB Output is correct

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 701 ms 186768 KB Output is correct

Subtask #3
0.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 0 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 701 ms 186768 KB Output is correct
5 Execution timed out 3694 ms 2037904 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 0 ms 336 KB Output is correct
3 Correct 655 ms 188480 KB Output is correct
4 Correct 829 ms 234568 KB Output is correct
5 Correct 734 ms 184136 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 652 ms 212064 KB Output is correct
8 Correct 649 ms 212040 KB Output is correct
9 Correct 630 ms 212160 KB Output is correct

Subtask #5
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 0 ms 336 KB Output is correct
3 Correct 655 ms 188480 KB Output is correct
4 Correct 829 ms 234568 KB Output is correct
5 Correct 734 ms 184136 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 652 ms 212064 KB Output is correct
8 Correct 649 ms 212040 KB Output is correct
9 Correct 630 ms 212160 KB Output is correct
10 Correct 460 ms 190284 KB Output is correct
11 Correct 488 ms 189000 KB Output is correct
12 Correct 500 ms 179792 KB Output is correct
13 Correct 517 ms 200604 KB Output is correct
14 Correct 531 ms 200776 KB Output is correct
15 Correct 524 ms 201148 KB Output is correct
16 Correct 261 ms 165568 KB Output is correct

Subtask #6
0.0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 0 ms 336 KB Output is correct
3 Correct 8 ms 4688 KB Output is correct
4 Correct 7 ms 3408 KB Output is correct
5 Correct 9 ms 4176 KB Output is correct
6 Correct 12 ms 6852 KB Output is correct
7 Correct 7 ms 2896 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 8 ms 4688 KB Output is correct
10 Correct 8 ms 4704 KB Output is correct
11 Correct 8 ms 4688 KB Output is correct
12 Correct 8 ms 4688 KB Output is correct
13 Correct 9 ms 4688 KB Output is correct
14 Correct 4 ms 3152 KB Output is correct
15 Correct 1 ms 336 KB Output is correct
16 Correct 701 ms 186768 KB Output is correct
17 Execution timed out 3694 ms 2037904 KB Time limit exceeded
18 Halted 0 ms 0 KB -