Submission #1075550

#	Time	Username	Problem	Language	Result	Execution time	Memory
1075550		ProtonDecay314	Petrol stations (CEOI24_stations)	C++17	0 / 100	3552 ms	5312 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;
};

vi solve(int n, int k, const vvpi& adj) {
    vi ans(n, 0);

    for(int s = 0; s < n; s++) {
        queue<state> q;

        q.push({s, s, k});

        while(!q.empty()) {
            auto [i, p, fuel] = q.front();

            q.pop();

            for(auto [j, l] : adj[i]) {
                if(j == p) continue;

                if(fuel < l) {
                    ans[i] ++;

                    q.push({j, i, k - l});
                } else {
                    q.push({j, i, fuel - l});
                }
            }
        }
    }

    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 << " ";

    cout << "\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