제출 #527711

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
527711		joelau	Parkovi (COCI22_parkovi)	C++14	110 / 110	1490 ms	33708 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] != -1) {
            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);
        }
    }
    if (dp1[x]+dp2[x] <= val) dp2[x] = -1;
}

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 (dp2[0] != -1) ans[0] = 1;
        if (ans.count() > K) low = val;
        else high = val;
    }
    cout << high << '\n';
    val = high;
    ans.reset();
    dfs(0,-1);
    if (dp2[0] != -1) 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;
}

컴파일 시 표준 에러 (stderr) 메시지

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

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