Submission #545513

#	Time	Username	Problem	Language	Result	Execution time	Memory
545513		mat50013	Parkovi (COCI22_parkovi)	C++11	40 / 110	950 ms	33120 KiB

Main

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
const int NMAX(200005);
const ll MAXX(1e16);
vector<pair<int, int> > G[NMAX];
vector<int> aux;
int n, k, fr[NMAX];
ll dis[NMAX];

inline pair<ll, ll> DFS(int nod, int tata, ll cat, ll dUnd)
{
    pair<ll, ll> sol = {MAXX, -MAXX};
    for(auto it: G[nod])
        if(it.first != tata)
        {
            auto ce = DFS(it.first, nod, cat, it.second);
            if(ce.first != MAXX)
                sol.first = min(sol.first, ce.first + it.second);
            if(ce.second != -MAXX)
                sol.second = max(sol.second, ce.second + it.second);
        }
    if(G[nod].size() == 1 && tata != -1)
    {
        if(dUnd > cat)
        {
            aux.push_back(nod);
            return {0, -MAXX};
        }
        return {MAXX, 0};
    }
    if(sol.first != MAXX && sol.first > cat && sol.second < 0)
    {
        sol.first = MAXX;
        sol.second = 0;
    }
    if(sol.first != MAXX && sol.second != -MAXX && sol.first + sol.second <= cat)
    {
        sol.second = -MAXX;
        return sol;
    }
    if((sol.first != MAXX && sol.second != -MAXX && sol.first + sol.second > cat) || (sol.second != -MAXX && sol.second > cat) || (sol.second != -MAXX && sol.second + dUnd > cat) || (nod == 1 && sol.second >= 0))
    {
        aux.push_back(nod);
        return {0, -MAXX};
    }
    return sol;
}

inline bool test(ll mij, int nr)
{
    aux.clear();
    DFS(1, -1, mij, 0);
    return ((int)aux.size() <= nr);
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    cin >> n >> k;

    for(int i = 1; i < n; ++i)
    {
        int x, y, c;
        cin >> x >> y >> c;
        G[x].push_back({y, c});
        G[y].push_back({x, c});
    }

    vector<int> sol;
    ll st = 0, dr = 1e16, best = 0;
    while(st <= dr)
    {
        ll mij = st + (dr - st) / 2;
        if(test(mij, k))
        {
            best = mij;
            sol = aux;
            dr = mij - 1;
        }
        else st = mij + 1;
    }

    cout << best << '\n';
    for(auto it: sol)
        fr[it] = 1;
    for(int i = 1; i <= n && (int)sol.size() < k; ++i)
        if(fr[i] == 0)
            sol.push_back(i);
    for(auto it: sol)
        cout << it << ' ';
    return 0;
}

• Subtask 1: 0 / 10
• Subtask 2: 10 / 10
• Subtask 3: 30 / 30
• Subtask 4: 0 / 60