oj.uz

Submission #1085816

# Submission time Handle Problem Language Result Execution time Memory
1085816 2024-09-08T18:38:58 Z hqminhuwu Parkovi (COCI22_parkovi) C++14
30 / 110
 554 ms 44228 KB 
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair <ll,ll> pll;
typedef pair <int,int> pii;
typedef pair <int,pii> piii;

#define forr(_a,_b,_c) for(int _a = (_b); _a <= int (_c); ++_a)
#define ford(_a,_b,_c) for(int _a = (_b) + 1; _a --> int (_c);)
#define forf(_a,_b,_c) for(int _a = (_b); _a < int (_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 int N = 5e5 + 5;
const ll oo = (ll) 2e16;
const ll mod = 1e9 + 7; // 998244353;

int deg[N], n, u, v, w, k;
ll dist[N], park[N];
stack <int> leaf;
int rem[N];
vector <pll> a[N];
vector <int> trace;

void dfs (int u, ll d, ll x){
    rem[u] = 1;
    dist[u] = -oo;
   // cout << u << " " << d << " ff" << endl;

    for (pll v : a[u]){
        if (rem[v.st]) continue;
        if (d + v.nd <= x){
            dfs(v.st, d + v.nd, x);
        } else {
            deg[v.st]--;
          //   cout << v.st << " " << deg[v.st] << endl;
            if (deg[v.st] == 1){
                leaf.push(v.st);
            }
        }
    }
}

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

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

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

        rem[u] = 1;
        ll tmp = oo;

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

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

      //  cout << u << " " << tmp << endl;

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

        if (tmp > x){
            trace.pb(u);
            dist[u] = -oo;
            for (pll v : a[u]){
                if (rem[v.st]) continue;
                if (v.nd <= x)
                    dfs(v.st, v.nd, 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 = 60, r = 60;

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

    
    solve(l);

    cout << l << "\n";


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

    k -= trace.size();

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

    sort(all(trace));

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



*/

Subtask #1
0 / 10.0

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

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 140 ms 39936 KB Output is correct
2 Correct 159 ms 41808 KB Output is correct
3 Correct 259 ms 38588 KB Output is correct
4 Incorrect 554 ms 37304 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 176 ms 42836 KB Output is correct
2 Correct 153 ms 42324 KB Output is correct
3 Correct 151 ms 41812 KB Output is correct
4 Correct 158 ms 40532 KB Output is correct
5 Correct 195 ms 44228 KB Output is correct
6 Correct 206 ms 43464 KB Output is correct
7 Correct 205 ms 44044 KB Output is correct
8 Correct 173 ms 42068 KB Output is correct
9 Correct 159 ms 42064 KB Output is correct
10 Correct 150 ms 41684 KB Output is correct
11 Correct 158 ms 40536 KB Output is correct
12 Correct 212 ms 44160 KB Output is correct
13 Correct 205 ms 43868 KB Output is correct
14 Correct 192 ms 42956 KB Output is correct
15 Correct 147 ms 41148 KB Output is correct
16 Correct 152 ms 40020 KB Output is correct
17 Correct 138 ms 40016 KB Output is correct
18 Correct 153 ms 40540 KB Output is correct
19 Correct 160 ms 41924 KB Output is correct
20 Correct 160 ms 37356 KB Output is correct
21 Correct 170 ms 36428 KB Output is correct

Subtask #4
0 / 60.0

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