oj.uz

답안 #1100700

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1100700 2024-10-14T13:15:06 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() {
    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

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 5880 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 5880 KB Output is correct
2 Correct 2 ms 5712 KB Output is correct
3 Correct 10 ms 9808 KB Output is correct
4 Correct 8 ms 8704 KB Output is correct
5 Correct 7 ms 9432 KB Output is correct
6 Correct 16 ms 12112 KB Output is correct
7 Correct 7 ms 8284 KB Output is correct
8 Correct 2 ms 5712 KB Output is correct
9 Correct 9 ms 9828 KB Output is correct
10 Correct 9 ms 10064 KB Output is correct
11 Correct 9 ms 10064 KB Output is correct
12 Correct 9 ms 10064 KB Output is correct
13 Correct 9 ms 10064 KB Output is correct
14 Correct 5 ms 8188 KB Output is correct

Subtask #2
8.0 / 8.0

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

Subtask #3
0.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 5880 KB Output is correct
2 Correct 2 ms 5712 KB Output is correct
3 Correct 2 ms 5712 KB Output is correct
4 Correct 613 ms 185660 KB Output is correct
5 Execution timed out 3547 ms 2097152 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 5880 KB Output is correct
2 Correct 2 ms 5712 KB Output is correct
3 Correct 616 ms 188520 KB Output is correct
4 Correct 726 ms 233288 KB Output is correct
5 Correct 633 ms 183096 KB Output is correct
6 Correct 2 ms 5712 KB Output is correct
7 Correct 593 ms 212020 KB Output is correct
8 Correct 605 ms 211948 KB Output is correct
9 Correct 622 ms 212044 KB Output is correct

Subtask #5
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 5880 KB Output is correct
2 Correct 2 ms 5712 KB Output is correct
3 Correct 616 ms 188520 KB Output is correct
4 Correct 726 ms 233288 KB Output is correct
5 Correct 633 ms 183096 KB Output is correct
6 Correct 2 ms 5712 KB Output is correct
7 Correct 593 ms 212020 KB Output is correct
8 Correct 605 ms 211948 KB Output is correct
9 Correct 622 ms 212044 KB Output is correct
10 Correct 405 ms 190028 KB Output is correct
11 Correct 472 ms 188960 KB Output is correct
12 Correct 497 ms 179852 KB Output is correct
13 Correct 517 ms 200736 KB Output is correct
14 Correct 512 ms 200776 KB Output is correct
15 Correct 501 ms 200776 KB Output is correct
16 Correct 216 ms 165004 KB Output is correct

Subtask #6
0.0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 5880 KB Output is correct
2 Correct 2 ms 5712 KB Output is correct
3 Correct 10 ms 9808 KB Output is correct
4 Correct 8 ms 8704 KB Output is correct
5 Correct 7 ms 9432 KB Output is correct
6 Correct 16 ms 12112 KB Output is correct
7 Correct 7 ms 8284 KB Output is correct
8 Correct 2 ms 5712 KB Output is correct
9 Correct 9 ms 9828 KB Output is correct
10 Correct 9 ms 10064 KB Output is correct
11 Correct 9 ms 10064 KB Output is correct
12 Correct 9 ms 10064 KB Output is correct
13 Correct 9 ms 10064 KB Output is correct
14 Correct 5 ms 8188 KB Output is correct
15 Correct 2 ms 5712 KB Output is correct
16 Correct 613 ms 185660 KB Output is correct
17 Execution timed out 3547 ms 2097152 KB Time limit exceeded
18 Halted 0 ms 0 KB -