Submission #1214480

#	Time	Username	Problem	Language	Result	Execution time	Memory
1214480		spetr	Petrol stations (CEOI24_stations)	C++20	0 / 100	174 ms	11380 KiB

Main

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int N;
ll K;
vector<vector<pair<int,ll>>> g;
vector<bool> removed;
vector<int> subsize;
vector<ll> ans;

// spočítá velikost podstromu u
int dfs_size(int u, int p) {
    subsize[u] = 1;
    for (auto [v,w]: g[u]) if (v!=p && !removed[v])
        subsize[u] += dfs_size(v,u);
    return subsize[u];
}

// najde centroid podstromu velikosti n v kořeni u
int find_centroid(int u, int p, int n) {
    for (auto [v,w]: g[u]) if (v!=p && !removed[v])
        if (subsize[v] > n/2)
            return find_centroid(v,u,n);
    return u;
}

// sesbírá vzdálenosti z u do všech uzlů v jeho komponentě
void dfs_dist(int u, int p, ll d, vector<ll>& D) {
    D.push_back(d);
    for (auto [v,w]: g[u]) if (v!=p && !removed[v])
        dfs_dist(v,u,d + w, D);
}

void decompose(int entry) {
    int n = dfs_size(entry,-1);
    int c = find_centroid(entry,-1,n);
    removed[c] = true;

    // pro centroid c budeme sbírat a slučovat vzdálenosti
    vector<ll> acc = {0};
    for (auto [v,w]: g[c]) if (!removed[v]) {
        vector<ll> D;
        dfs_dist(v, c, w, D);
        sort(D.begin(), D.end());
        sort(acc.begin(), acc.end());
        // spočítat oriented dvojice mezi D a acc, kde d1 + d2 > K
        ll cnt = 0;
        int i = 0, j = acc.size()-1;
        while (i < (int)D.size() && j >= 0) {
            if (D[i] + acc[j] > K) {
                cnt += j+1;
                i++;
            } else {
                j--;
            }
        }
        // každá taková dvojice je orientovaná oběma směry
        ans[c] += cnt * 2;
        // merge D do acc
        acc.insert(acc.end(), D.begin(), D.end());
    }

    // rekurzivně na podkomponenty
    for (auto [v,w]: g[c]) if (!removed[v])
        decompose(v);
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> N >> K;
    g.assign(N, {});
    for (int i = 0; i < N-1; i++){
        int u,v; ll l;
        cin >> u >> v >> l;
        g[u].emplace_back(v,l);
        g[v].emplace_back(u,l);
    }

    removed.assign(N,false);
    subsize.assign(N,0);
    ans.assign(N,0);

    decompose(0);

    // výstup
    for (int i = 0; i < N; i++)
        cout << ans[i] << "\n";

    return 0;
}

• Subtask 0: 0 / 0
• Subtask 1: 0 / 18
• Subtask 2: 0 / 8
• Subtask 3: 0 / 10
• Subtask 4: 0 / 12
• Subtask 5: 0 / 17
• Subtask 6: 0 / 35