Submission #955933

#	Time	Username	Problem	Language	Result	Execution time	Memory
955933		dosts	Parkovi (COCI22_parkovi)	C++17	30 / 110	3045 ms	32516 KiB

Main

//Dost SEFEROĞLU
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define F(xxx,yyy) for (int xxx=0;xxx<yyy;xxx++)
#define pii pair<int,int>
#define ff first
#define ss second
#define sp << " " << 
#define vi vector<int>
const int N = 2e5+1,inf = 2e18,MOD = 1e9+7;

vector<pii> edges[N];
vi d(N),p(N);

void dfs(int node,int pp,int dd=0) {
    d[node] = dd;
    p[node] = pp;
    for (auto it : edges[node]) {
        if (it.ff == pp) continue;
        dfs(it.ff,node,dd+it.second);
    }
}

void solve() {
    int n,k;
    cin >> n >> k;
    for (int i=1;i<=n;i++) {
        int a,b,c;
        cin >> a >> b >> c;
        edges[a].push_back({b,c});
        edges[b].push_back({a,c});
    }
    dfs(1,1);
    vi order(n+1);
    for (int i=1;i<=n;i++) order[i] = i;
    sort(order.begin()+1,order.end(),[&](int x,int y) {
        return d[x] > d[y];
    });
    vi done(n+1);
    auto f = [&](int x,bool debug = 0) {
        done.assign(n+1,0);
        int ans = 0;
        for (int i=1;i<=n;i++) {
            int nd = order[i];
            if (done[nd]) continue;
            ans++;
            int cur = nd;
            int curdist = 0;
            while (curdist <= x && cur != 1) {
                if (curdist+(d[cur]-d[p[cur]]) <= x) {
                    curdist+=(d[cur]-d[p[cur]]);
                    cur = p[cur];
                } else break;
            }
            if (debug) cout << nd sp cur << endl;
            queue<pii> q;
            q.push({cur,0});
            done[cur] = 2;
            while (!q.empty()) {
                pii f = q.front();
                q.pop();
                for (auto it : edges[f.ff]) {
                    if (done[it.ff]) continue;
                    if (f.ss+it.ss > x) continue;
                    done[it.ff] = 1;
                    q.push({it.ff,it.ss+f.ss});
                }
            }
        }
        if (debug) cout << endl;
        return ans;
    };
    //f(8,1);
    int l = 0;
    int r = 1e18;
    while (l<=r) {
        int m = (l+r) >> 1;
        int x = f(m);
        //cout << "TRY : " << m sp "gives" sp x<< endl;
        if (x <= k) r = m-1;
        else l = m+1;
    }
    f(l);
    cout << l << endl;
    for (int i=1;i<=n;i++) {
        if (done[i] == 2) {
            k--;
            cout << i;
            if (k) cout << " ";
        }
    }
    if (k) {
        for (int i=1;i<=n;i++) {
            if (k && done[i] != 2) {
                k--;
                cout << i << " ";
            }
        }
        cout << endl;
    }
    else cout << endl;
}
                 
                             
signed main() { 
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    #ifdef Dodi
        freopen("in.txt","r",stdin);
        freopen("out.txt","w",stdout);
    #endif
    int t = 1;
    //cin >> t; 
    while (t --> 0) solve();
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 30 / 30
• Subtask 4: 0 / 60