Submission #527709

#	Time	Username	Problem	Language	Result	Execution time	Memory
527709		joelau	Parkovi (COCI22_parkovi)	C++14	0 / 110	325 ms	32640 KiB

Main

#include <bits/stdc++.h>
using namespace std;

long long N,K, dp1[200005], dp2[200005], val, inf = 1e18;
vector< pair<long long,long long> > lst[200005];
bitset<200005> ans;

void dfs (long long x, long long p) {
    dp1[x] = inf, dp2[x] = 0;
    for (auto v: lst[x]) if (v.first != p) {
        dfs(v.first,x);
        dp1[x] = min(dp1[x],dp1[v.first] + v.second);
        if (dp2[v.first] + v.second > val) ans[v.first] = 1, dp1[x] = min(dp1[x],v.second);
        else dp2[x] = max(dp2[x],dp2[v.first] + v.second);
    }
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    cin >> N >> K;
    for (long long i = 0; i < N-1; ++i) {
        long long u,v,w; cin >> u >> v >> w; u--, v--;
        lst[u].emplace_back(v,w), lst[v].emplace_back(u,w);
    }
    long long low = -1, high = 2e14;
    while (high - low > 1) {
        val = (low+high)/2;
        ans.reset();
        dfs(0,-1);
        if (dp1[0]+dp2[0] > val) ans[0] = 1;
        if (ans.count() > K) low = val;
        else high = val;
    }
    cout << high << '\n';
    val = high;
    ans.reset();
    dfs(0,-1);
    if (dp1[0]+dp2[0] > val) ans[0] = 1;
    for (long long i = 0, num = ans.count(); i < N && num < K; ++i) if (!ans[i]) ans[i] = 1, num++;
    for (long long i = 0; i < N; ++i) if (ans[i]) cout << i+1 << ' ';

    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:31:25: warning: comparison of integer expressions of different signedness: 'std::size_t' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   31 |         if (ans.count() > K) low = val;
      |             ~~~~~~~~~~~~^~~

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