제출 #1072747

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1072747		jer033	Petrol stations (CEOI24_stations)	C++17	18 / 100	3553 ms	9620 KiB

Main

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

vector<ll> answers;

void root_and_fill(vector<vector<pil>> (&edges), int root, ll K)
{
    int N = edges.size();
    vector<bool> visited(N, 0);
    visited[root] = 1;
    vector<int> visitlist;
    visitlist.push_back(root);
    vector<int> parent(N, -1);
    int vsize = 1;
    int curri = 0;
    while (curri<vsize)
    {
        int curr_city = visitlist[curri];
        curri++;
        for (pil neigh: edges[curr_city])
        {
            int a = neigh.first;
            if (visited[a] == 0)
            {
                visited[a] = 1;
                visitlist.push_back(a);
                vsize++;
                parent[a] = curr_city;
            }
        }
    }
    vector<ll> degree(N, 1);
    for (int i=N-1; i>=1; i--)
    {
        int curr_city = visitlist[i];
        degree[parent[curr_city]] += degree[curr_city];
    }

    vector<ll> tanks(N, K);
    for (int i=1; i<N; i++)
    {
        int curr_city = visitlist[i];
        ll cost = 0;
        for (pil neigh: edges[curr_city])
        {
            if (neigh.first == parent[curr_city])
                cost = neigh.second;
        }
        tanks[curr_city] = tanks[parent[curr_city]];
        tanks[curr_city] -= cost;
        if (tanks[curr_city] < 0ll)
        {
            tanks[curr_city] = K-cost;
            answers[parent[curr_city]] += degree[curr_city];
        }
    }
}

int main()
{
    std::ios_base::sync_with_stdio(false);
    ll N, K;
    cin >> N >> K;
    answers = vector<ll> (N, 0);
    vector<vector<pil>> edges(N);
    for (ll i=0; i<(N-1); i++)
    {
        int u, v; ll L;
        cin >> u >> v >> L;
        edges[u].push_back({v, L});
        edges[v].push_back({u, L});
    }

    for (ll i = 0; i<N; i++)
        root_and_fill(edges, i, K);
    for (ll i = 0; i<N; i++)
        cout << answers[i] << '\n';
}

• 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