oj.uz

Submission #545511

# Submission time Handle Problem Language Result Execution time Memory
545511 2022-04-04T17:02:00 Z mat50013 Parkovi (COCI22_parkovi) C++11
40 / 110
 1106 ms 35896 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, -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.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 5020 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 4 ms 4948 KB Output is correct
7 Correct 3 ms 4948 KB Output is correct
8 Incorrect 3 ms 5024 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 345 ms 28484 KB Output is correct
2 Correct 385 ms 31940 KB Output is correct
3 Correct 287 ms 16348 KB Output is correct
4 Correct 1077 ms 14712 KB Output is correct
5 Correct 971 ms 14476 KB Output is correct
6 Correct 970 ms 14604 KB Output is correct
7 Correct 991 ms 14460 KB Output is correct
8 Correct 1052 ms 14832 KB Output is correct
9 Correct 1016 ms 14684 KB Output is correct
10 Correct 1106 ms 14928 KB Output is correct
11 Correct 609 ms 16036 KB Output is correct
12 Correct 721 ms 16416 KB Output is correct
13 Correct 748 ms 17264 KB Output is correct
14 Correct 661 ms 16188 KB Output is correct
15 Correct 681 ms 15704 KB Output is correct
16 Correct 667 ms 16416 KB Output is correct
17 Correct 638 ms 15720 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 434 ms 29552 KB Output is correct
2 Correct 407 ms 31620 KB Output is correct
3 Correct 348 ms 30340 KB Output is correct
4 Correct 351 ms 30292 KB Output is correct
5 Correct 399 ms 34652 KB Output is correct
6 Correct 408 ms 34356 KB Output is correct
7 Correct 433 ms 35548 KB Output is correct
8 Correct 392 ms 32384 KB Output is correct
9 Correct 396 ms 32224 KB Output is correct
10 Correct 384 ms 31664 KB Output is correct
11 Correct 347 ms 30808 KB Output is correct
12 Correct 462 ms 35608 KB Output is correct
13 Correct 450 ms 35896 KB Output is correct
14 Correct 420 ms 34216 KB Output is correct
15 Correct 383 ms 31604 KB Output is correct
16 Correct 354 ms 30592 KB Output is correct
17 Correct 353 ms 30504 KB Output is correct
18 Correct 397 ms 31788 KB Output is correct
19 Correct 364 ms 34032 KB Output is correct
20 Correct 377 ms 34248 KB Output is correct
21 Correct 361 ms 33312 KB Output is correct

Subtask #4
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 5020 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 4 ms 4948 KB Output is correct
7 Correct 3 ms 4948 KB Output is correct
8 Incorrect 3 ms 5024 KB Output isn't correct
9 Halted 0 ms 0 KB -