oj.uz

Submission #537550

# Submission time Handle Problem Language Result Execution time Memory
537550 2022-03-15T08:18:38 Z topovik Parkovi (COCI22_parkovi) C++14
0 / 110
 872 ms 58116 KB 
#include <bits/stdc++.h>
#define pb push_back
#define f first
#define s second

using namespace std;

typedef long long ll;
typedef long double ld;

const ll N = 1e6 + 100;
const ll M = 1e3 + 10;
const ll oo = 1e18 + 7;

vector <pair<ll, ll> > a[N];

ll n, k;
ll mx_ds;
ll kol;
pair<ll, ll> dp[N];

set <ll> ans;
bool g = 0;

pair<ll, ll> Rec(ll x, ll y)
{
    vector <pair<ll, ll> > vc;
    ll up = 0;
    for (auto i : a[x])
        if (i.f != y) vc.pb(Rec(i.f, x));
        else up = i.s;
    sort(vc.begin(), vc.end());
    ll mx = 0;
    ll mn = (vc.size() > 0 ? vc[0].f : oo);
    for (auto i : vc)
        if (mn + i.s > mx_ds) mx = max(mx, i.s);
    if (mx + up > mx_ds && (mx != 0 || mn > mx_ds))
    {
        if (g) ans.insert(x);
        kol++;
        mx = 0;
        mn = 0;
    }
    if (x == 0 && (mx != 0 || mn > mx_ds))
    {
        if (g) ans.insert(x);
        kol++;
        return {0, 0};
    }

    mx += up;
    if (mx == up && mn <= mx_ds) mx = 0;
    mn += up;
    if (mn > mx_ds) mx = oo;
    return {mn, mx};
}

bool Check(ll x)
{
    mx_ds = x;
    kol = 0;
    Rec(0, 0);
    return kol <= k;
}

int main()
{
    ios_base::sync_with_stdio(0);
    iostream::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> k;
    for (ll i = 0; i < n - 1; i++)
    {
        ll x, y, z;
        cin >> x >> y >> z;
        a[--x].pb({--y, z});
        a[y].pb({x, z});
    }
    ll l = 0, r = oo;
    while (l < r)
    {
        ll mdl = (l + r) >> 1;
        if (Check(mdl)) r = mdl;
        else l = mdl + 1;
    }
    cout << l << endl;
    g = 1;
    Check(l);
    int i = 0;
    while (ans.size() < k) ans.insert(i++);
    for (auto i : ans) cout << i + 1 << " ";
}
/*
5 1
1 2 3
2 3 4
3 4 5
4 5 6
*/

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:91:23: warning: comparison of integer expressions of different signedness: 'std::set<long long int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
   91 |     while (ans.size() < k) ans.insert(i++);
      |            ~~~~~~~~~~~^~~

Subtask #1
0 / 10.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 30.0

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

Subtask #4
0 / 60.0

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