oj.uz

Submission #545509

# Submission time Handle Problem Language Result Execution time Memory
545509 2022-04-04T16:45:17 Z mat50013 Parkovi (COCI22_parkovi) C++11
0 / 110
 374 ms 31924 KB 
#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 != -1)
                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, -1};
        }
        return {MAXX, 0};
    }
    if(sol.first != MAXX && sol.first > cat && sol.second < 0)
        sol.second = 0;
    if(sol.first != MAXX && sol.second != -1 && sol.first + sol.second <= cat)
        sol.second = -1;
    if(sol.second != -1 && sol.second + dUnd > cat)
    {
        aux.push_back(nod);
        return {0, -1};
    }
    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.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 4948 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 343 ms 30132 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 374 ms 31924 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 60.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 4948 KB Output isn't correct
2 Halted 0 ms 0 KB -