oj.uz

Submission #1100695

# Submission time Handle Problem Language Result Execution time Memory
1100695 2024-10-14T13:01:01 Z not_amir Petrol stations (CEOI24_stations) C++14
55 / 100
 3500 ms 995856 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() {
    srand(time(nullptr));
    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});
    }
    int v = rand() % n;
    centroid_decomp(v, 1);
    sort(vals.begin(), vals.end());
    for(int x : vals)
        cmp[x] = INF++;
    is_removed.clear();
    is_removed.resize(n);
    centroid_decomp(v, 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 13 ms 5968 KB Output is correct
4 Correct 13 ms 6992 KB Output is correct
5 Correct 9 ms 3688 KB Output is correct
6 Correct 17 ms 7644 KB Output is correct
7 Correct 7 ms 2640 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 10 ms 4432 KB Output is correct
10 Correct 10 ms 4688 KB Output is correct
11 Correct 11 ms 4860 KB Output is correct
12 Correct 11 ms 4688 KB Output is correct
13 Correct 9 ms 4688 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 508 KB Output is correct
2 Correct 1609 ms 574932 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 508 KB Output is correct
4 Correct 1609 ms 574932 KB Output is correct
5 Execution timed out 3609 ms 995856 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 1318 ms 522680 KB Output is correct
4 Correct 1839 ms 729444 KB Output is correct
5 Correct 967 ms 225184 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1248 ms 466628 KB Output is correct
8 Correct 1317 ms 467624 KB Output is correct
9 Correct 1235 ms 466692 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 1318 ms 522680 KB Output is correct
4 Correct 1839 ms 729444 KB Output is correct
5 Correct 967 ms 225184 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1248 ms 466628 KB Output is correct
8 Correct 1317 ms 467624 KB Output is correct
9 Correct 1235 ms 466692 KB Output is correct
10 Correct 647 ms 309928 KB Output is correct
11 Correct 788 ms 359344 KB Output is correct
12 Correct 757 ms 331108 KB Output is correct
13 Correct 882 ms 375216 KB Output is correct
14 Correct 924 ms 383024 KB Output is correct
15 Correct 843 ms 383220 KB Output is correct
16 Correct 293 ms 176008 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 13 ms 5968 KB Output is correct
4 Correct 13 ms 6992 KB Output is correct
5 Correct 9 ms 3688 KB Output is correct
6 Correct 17 ms 7644 KB Output is correct
7 Correct 7 ms 2640 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 10 ms 4432 KB Output is correct
10 Correct 10 ms 4688 KB Output is correct
11 Correct 11 ms 4860 KB Output is correct
12 Correct 11 ms 4688 KB Output is correct
13 Correct 9 ms 4688 KB Output is correct
14 Correct 4 ms 2128 KB Output is correct
15 Correct 1 ms 508 KB Output is correct
16 Correct 1609 ms 574932 KB Output is correct
17 Execution timed out 3609 ms 995856 KB Time limit exceeded
18 Halted 0 ms 0 KB -