Submission #1075624

#	Time	Username	Problem	Language	Result	Execution time	Memory
1075624		ProtonDecay314	Petrol stations (CEOI24_stations)	C++17	18 / 100	3560 ms	12092 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;
}

vi solve(int n, int k, const vvpi& adj) {
    // Root the tree at zero
    vvi adjtree;
    for(int i = 0; i < n; i++) {
        vi adjtreer;
        adjtree.pb(adjtreer);
    }

    queue<pi> q1;
    q1.push({0, 0});

    while(!q1.empty()) {
        auto [i, p] = q1.front();
        if(i != p) adjtree[p].pb(i);

        q1.pop();

        for(auto [j, _]: adj[i]) {
            if(j == p) continue;
            q1.push({j, i});
        }
    }


    // Compute heights and subtree sizes
    vi depth(n, 0);
    vi tree_sz(n, 0);

    compute_depth(0, 0, adjtree, depth);
    // cout << "Anya likes peanuts" << endl;
    compute_size(0, adjtree, tree_sz);

    // BFS time
    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) {
                    if(depth[j] > depth[i]) {
                        // Case 1: i->j descends, then the number of paths
                        // is the subtree size of j
                        ans[i] += tree_sz[j];
                    } else {
                        // Case 2: i->j ascends, then the number of paths is
                        // n - subtree size i
                        ans[i] += n - tree_sz[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 << "\n";

    cout << flush;

    return 0;
}

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