oj.uz

Submission #545513

# Submission time Handle Problem Language Result Execution time Memory
545513 2022-04-04T17:10:07 Z mat50013 Parkovi (COCI22_parkovi) C++11
40 / 110
 950 ms 33120 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 != -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.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Correct 3 ms 4948 KB Output is correct
8 Incorrect 2 ms 4948 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 28516 KB Output is correct
2 Correct 364 ms 29176 KB Output is correct
3 Correct 234 ms 13616 KB Output is correct
4 Correct 950 ms 12000 KB Output is correct
5 Correct 848 ms 11784 KB Output is correct
6 Correct 852 ms 11744 KB Output is correct
7 Correct 883 ms 11916 KB Output is correct
8 Correct 942 ms 12236 KB Output is correct
9 Correct 876 ms 12072 KB Output is correct
10 Correct 948 ms 12296 KB Output is correct
11 Correct 599 ms 13476 KB Output is correct
12 Correct 571 ms 13728 KB Output is correct
13 Correct 670 ms 14548 KB Output is correct
14 Correct 556 ms 13508 KB Output is correct
15 Correct 550 ms 13128 KB Output is correct
16 Correct 584 ms 13792 KB Output is correct
17 Correct 572 ms 13072 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 371 ms 29652 KB Output is correct
2 Correct 377 ms 28856 KB Output is correct
3 Correct 333 ms 27556 KB Output is correct
4 Correct 337 ms 27724 KB Output is correct
5 Correct 376 ms 32008 KB Output is correct
6 Correct 387 ms 31740 KB Output is correct
7 Correct 415 ms 32688 KB Output is correct
8 Correct 372 ms 29700 KB Output is correct
9 Correct 362 ms 29492 KB Output is correct
10 Correct 341 ms 29000 KB Output is correct
11 Correct 332 ms 28084 KB Output is correct
12 Correct 409 ms 32996 KB Output is correct
13 Correct 412 ms 33120 KB Output is correct
14 Correct 398 ms 31460 KB Output is correct
15 Correct 335 ms 29028 KB Output is correct
16 Correct 342 ms 27980 KB Output is correct
17 Correct 328 ms 27852 KB Output is correct
18 Correct 338 ms 29260 KB Output is correct
19 Correct 347 ms 31372 KB Output is correct
20 Correct 358 ms 31580 KB Output is correct
21 Correct 362 ms 30724 KB Output is correct

Subtask #4
0 / 60.0

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