oj.uz

Submission #1086043

# Submission time Handle Problem Language Result Execution time Memory
1086043 2024-09-09T11:25:28 Z hqminhuwu Parkovi (COCI22_parkovi) C++14
10 / 110
 2337 ms 36908 KB 
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair <ll,ll> pll;
typedef pair <ll,ll> pii;
typedef pair <ll,pii> piii;

#define forr(_a,_b,_c) for(ll _a = (_b); _a <= ll (_c); ++_a)
#define ford(_a,_b,_c) for(ll _a = (_b) + 1; _a --> ll (_c);)
#define forf(_a,_b,_c) for(ll _a = (_b); _a < ll (_c); ++_a)
#define st first
#define nd second
#define pb push_back
#define mp make_pair
#define all(x) begin(x),end(x)
#define mask(i) (1LL << (i))
#define bit(x, i) (((x) >> (i)) & 1)
#define bp __builtin_popcountll
#define file "test"

template<class X, class Y>
    bool minz(X &x, const Y &y) {
        if (x > y) {
            x = y;
            return true;
        } return false;
    }
template<class X, class Y>
    bool maxz(X &x, const Y &y) {
        if (x < y) {
            x = y;
            return true;
        } return false;
    }

const ll N = 5e5 + 5;
const ll oo = (ll) 2e16;
const ll mod = 1e9 + 7; // 998244353;

ll deg[N], n, u, v, w, k, cnt;
ll dist[N], park[N], flag[N];
priority_queue <pll, vector<pll>, greater<pll>> leaf;
ll rem[N];
vector <pll> a[N];
vector <ll> trace;

ll calcdist (ll u){
    dist[u] = -oo;
    flag[u] = 0;
    for (pll v : a[u]){
        if (rem[v.st]) flag[u] = 1;
        if (rem[v.st] && !(dist[v.st] < 0 && dist[v.st] + v.nd > 0)){
            dist[u] = max (dist[u], dist[v.st] + v.nd);
        }
    }
    if (dist[u] == -oo) dist[u] = 0;
    return dist[u];
}

ll solve(ll x){
    while (leaf.size()) leaf.pop();
    trace.clear();
    cnt = 0;

    forr (i, 1, n){
        rem[i] = 0;
        dist[i] = -2 * oo;
        deg[i] = a[i].size();
        if (a[i].size() == 1){
            leaf.push(mp(0, i));
        }
    }

    while (leaf.size()){
        ll u = leaf.top().nd;
        leaf.pop();
        if (rem[u]) continue;

        rem[u] = 1;
        dist[u] = -oo;
        cnt++;
        ll tmp = oo;

        calcdist(u);

        for (pll v : a[u]){
            if (rem[v.st]) continue;
            tmp = min (tmp, dist[u] + v.nd);
        }

      // cout << u << " " << tmp << " " << dist[u] << endl;

        for (pll v : a[u]){
            if (rem[v.st]) continue;
            deg[v.st]--;
            if (deg[v.st] == 1)
                leaf.push(mp(calcdist(v.st), v.st));
        }

        if (tmp == oo){
            ll ww = 0;
            for (pll v : a[u]){
                if (rem[v.st] && dist[u] + dist[v.st] + v.nd <= 0)
                    ww = 1;
            }

            if (ww) continue;
            //if (dist[u] > 0 || (dist[u] == 0 && !flag[u])){
            //    cout << u << ": " << endl;
                trace.pb(u);
                dist[u] = -x;
           // }
        } else
        if (tmp > x){
        //   cout << u << ": " << endl;
            trace.pb(u);
            dist[u] = -x;
        }
    }   

    return trace.size();
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    #ifdef hqm
        freopen(file".inp", "r", stdin); freopen(file".out", "w", stdout);
    #endif

    cin >> n >> k;

    forf (i, 1, n){
        cin >> u >> v >> w;
        a[u].pb({v, w});
        a[v].pb({u, w});
    }

    ll l = 0, r = oo;
   // l = 5, r = 5;

    while (l < r){
        ll mid = (l + r) >> 1;
        if (solve(mid) > k)
            l = mid + 1;
        else r = mid;
    }        

    
    solve(l);

    cout << l << "\n";


    for (ll u : trace){
        park[u] = 1;
    }

    k -= trace.size();

    forr (i, 1, n)
    if (!park[i] && k){
        k--;
        trace.pb(i);
    }

    //sort(all(trace));

    for (ll u : trace)
        cout << u << " ";
    
 
    return 0;
}
/*



*/

Subtask #1
0 / 10.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 362 ms 26708 KB Output is correct
2 Correct 353 ms 31476 KB Output is correct
3 Correct 1209 ms 36908 KB Output is correct
4 Correct 2305 ms 33216 KB Output is correct
5 Correct 2225 ms 32780 KB Output is correct
6 Correct 2115 ms 32808 KB Output is correct
7 Correct 2127 ms 31656 KB Output is correct
8 Correct 2337 ms 32536 KB Output is correct
9 Correct 2127 ms 32708 KB Output is correct
10 Correct 2273 ms 33224 KB Output is correct
11 Correct 1793 ms 32960 KB Output is correct
12 Correct 1765 ms 32436 KB Output is correct
13 Correct 2116 ms 34264 KB Output is correct
14 Correct 1733 ms 30672 KB Output is correct
15 Correct 1777 ms 30916 KB Output is correct
16 Correct 1904 ms 31980 KB Output is correct
17 Correct 1804 ms 31412 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 339 ms 31396 KB Output is correct
2 Incorrect 332 ms 31316 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 60.0

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