Submission #1072782

#	Time	Username	Problem	Language	Result	Execution time	Memory
1072782		jer033	Petrol stations (CEOI24_stations)	C++17	36 / 100	40 ms	14424 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];
        }
    }
}

void line(vector<vector<pil>> (&edges), int endpt, ll K)
{
    ll N = edges.size();
    vector<int> nodes;
    vector<ll> weights;//will have size N-1, access until N-2

    //collapsed at "while (good)"
    //creates the line
    nodes.push_back(endpt);
    int prev = -1;
    int curr = endpt;
    bool good = 1;
    while (good)
    {
        good = 0;
        int nex = -1;
        for (pil x: edges[curr])
        {
            int y = x.first;
            ll z = x.second;
            if (y!=prev)
            {
                nex = y;
                nodes.push_back(y);
                weights.push_back(z);
            }
        }
        if (nex!=-1)
        {
            good = 1;
            prev = curr;
            curr = nex;
        }
    }

    vector<ll> nex_refill(N, -1);
    ll i = 0;
    ll j = 0;
    ll currsum = 0;
    good = 1;//this is a bool value that I am reusing
    while (good)
    {
        if (currsum<=K)
        {
            if (j<=(N-2ll))
            {
                currsum+=weights[j];
                j++;
            }
            else
                good = 0;
        }
        else
        {
            currsum-=weights[i];
            nex_refill[i] = j-1;
            i++;
            //cout << "next refill of " << i << "  is  " << j-1 << '\n';
        }
    }

    vector<ll> refill_count(N, 0);
    for (ll r=0; r<N; r++)
    {
        if (nex_refill[r] != -1)
            refill_count[nex_refill[r]] += (refill_count[r]+1ll);
        ll add_times = refill_count[r] * (N-r-1ll);
        answers[nodes[r]] += add_times;
    }
}

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});
    }

    if ((N<=1000ll) and (K<=1000ll))
    {
        for (ll i = 0; i<N; i++)
            root_and_fill(edges, i, K);
        for (ll i = 0; i<N; i++)
            cout << answers[i] << '\n';
    }
    else
    {
        for (ll i = 0; i<N; i++)
            if (edges[i].size() == 1)
                line(edges, i, K);
        for (ll i = 0; i<N; i++)
            cout << answers[i] << '\n';
    }
}

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