oj.uz

답안 #1100699

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1100699 2024-10-14T13:13:32 Z not_amir Petrol stations (CEOI24_stations) C++14
55 / 100
 3500 ms 2062144 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 = 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);
    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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 5712 KB Output is correct
2 Correct 2 ms 5712 KB Output is correct
3 Correct 11 ms 9808 KB Output is correct
4 Correct 8 ms 8784 KB Output is correct
5 Correct 8 ms 9552 KB Output is correct
6 Correct 13 ms 12080 KB Output is correct
7 Correct 7 ms 8272 KB Output is correct
8 Correct 2 ms 5712 KB Output is correct
9 Correct 10 ms 9808 KB Output is correct
10 Correct 9 ms 10064 KB Output is correct
11 Correct 11 ms 10064 KB Output is correct
12 Correct 9 ms 10168 KB Output is correct
13 Correct 11 ms 10064 KB Output is correct
14 Correct 5 ms 8432 KB Output is correct

Subtask #2
8.0 / 8.0

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

Subtask #3
0.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 5712 KB Output is correct
2 Correct 2 ms 5712 KB Output is correct
3 Correct 2 ms 5712 KB Output is correct
4 Correct 652 ms 185720 KB Output is correct
5 Execution timed out 3692 ms 2062144 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 5712 KB Output is correct
2 Correct 2 ms 5712 KB Output is correct
3 Correct 670 ms 188508 KB Output is correct
4 Correct 779 ms 233288 KB Output is correct
5 Correct 692 ms 183120 KB Output is correct
6 Correct 3 ms 5888 KB Output is correct
7 Correct 636 ms 211968 KB Output is correct
8 Correct 633 ms 212040 KB Output is correct
9 Correct 591 ms 212040 KB Output is correct

Subtask #5
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 5712 KB Output is correct
2 Correct 2 ms 5712 KB Output is correct
3 Correct 670 ms 188508 KB Output is correct
4 Correct 779 ms 233288 KB Output is correct
5 Correct 692 ms 183120 KB Output is correct
6 Correct 3 ms 5888 KB Output is correct
7 Correct 636 ms 211968 KB Output is correct
8 Correct 633 ms 212040 KB Output is correct
9 Correct 591 ms 212040 KB Output is correct
10 Correct 405 ms 190128 KB Output is correct
11 Correct 467 ms 189000 KB Output is correct
12 Correct 461 ms 179784 KB Output is correct
13 Correct 538 ms 200776 KB Output is correct
14 Correct 512 ms 200740 KB Output is correct
15 Correct 523 ms 200736 KB Output is correct
16 Correct 252 ms 165308 KB Output is correct

Subtask #6
0.0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 5712 KB Output is correct
2 Correct 2 ms 5712 KB Output is correct
3 Correct 11 ms 9808 KB Output is correct
4 Correct 8 ms 8784 KB Output is correct
5 Correct 8 ms 9552 KB Output is correct
6 Correct 13 ms 12080 KB Output is correct
7 Correct 7 ms 8272 KB Output is correct
8 Correct 2 ms 5712 KB Output is correct
9 Correct 10 ms 9808 KB Output is correct
10 Correct 9 ms 10064 KB Output is correct
11 Correct 11 ms 10064 KB Output is correct
12 Correct 9 ms 10168 KB Output is correct
13 Correct 11 ms 10064 KB Output is correct
14 Correct 5 ms 8432 KB Output is correct
15 Correct 2 ms 5712 KB Output is correct
16 Correct 652 ms 185720 KB Output is correct
17 Execution timed out 3692 ms 2062144 KB Time limit exceeded
18 Halted 0 ms 0 KB -