Submission #1075694

#	Time	Username	Problem	Language	Result	Execution time	Memory
1075694		ProtonDecay314	Petrol stations (CEOI24_stations)	C++17	0 / 100	50 ms	6044 KiB

Main

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pi;
typedef vector<pi> vpi;
typedef vector<vpi> vvpi;
typedef pair<ll, ll> pll;
typedef vector<pll> vpll;
typedef vector<bool> vb;
typedef set<ll> sll;
#define IOS cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(false)
#define INF(dtype) numeric_limits<dtype>::max()
#define NINF(dtype) numeric_limits<dtype>::min()
#define fi first
#define se second
#define pb push_back

typedef vector<vb> vvb;
typedef vector<vvb> v3b;
typedef vector<v3b> v4b;
typedef vector<string> vs;

// struct state {
//     int i, p;
//     int fuel;
// };

// void compute_depth(int i, int d, const vvi& adj, vi& depth) {
//     depth[i] = d;

//     // cout << i << " " << d << endl;

//     for(int j : adj[i]) {
//         compute_depth(j, d + 1, adj, depth);
//     }
// }

// int compute_size(int i, const vvi& adj, vi& tree_sz) {
//     int& ans = tree_sz[i];

//     ans += 1;

//     for(int j : adj[i]) {
//         ans += compute_size(j, adj, tree_sz);
//     }

//     return ans;
// }

int solve(int i, int n, int k) {
    int nl = i / k;
    int nr = (n - i - 1) / k;

    return nl * (n - i - 1) + nr * i;
}

vi solve(int n, int k, const vvpi& adj) {
    vi ans(n, 0);
    
    // Find the starting point (i.e., the point of outdegree 1)
    int s = 0;

    for(int i = 0; i < n; i++) {
        if(adj[i].size() == 1) {
            s = i;
            break;
        }
    }

    int ind = 0;
    ans[s] = solve(0, n, k);

    int prev = s;
    for(int i = 0; i < n - 1; i++) {
        // Goto next
        // cout << s << " " << prev << endl;
        if(adj[s][0].fi != prev) {
            prev = s;
            s = adj[s][0].fi;
        } else {
            prev = s;
            s = adj[s][1].fi;
        }

        ind++;

        ans[s] = solve(ind, n, k);

        // cout << s << " ";
    }
    // cout << endl;

    return ans;
}

int main() {
    int n, k; cin >> n >> k;

    vvpi adj;
    for(int i = 0; i < n; i++) {
        vpi adjr;
        adj.pb(adjr);
    }

    for(int i = 0; i < n - 1; i++) {
        int u, v, l;
        cin >> u >> v >> l;

        adj[u].pb({v, l});
        adj[v].pb({u, l});
    }

    vi ans = solve(n, k, adj);

    for(int v : ans) cout << v << "\n";

    cout << flush;

    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