Submission #526730

#	Time	Username	Problem	Language	Result	Execution time	Memory
526730		joelau	Parkovi (COCI22_parkovi)	C++14	0 / 110	54 ms	5756 KiB

Main

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

long long N,K, A[200005];
bitset<200005> bs;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    cin >> N >> K;
    A[0] = 0;
    for (long long i = 1; i < N; ++i) {
        long long u,v,w; cin >> u >> v >> w; u--, v--;
        A[i] = A[i-1] + w;
    }
    long long low = -1, high = 200000000000000;
    while (high-low > 1) {
        long long mid = (low+high)/2, n = 0;
        while (n < N && A[n] <= mid) n++;
        long long num = 1;
        while (n < N) {
            long long a = n;
            while (a < N && A[a]-A[n-1] <= mid) a++;
            long long b = a;
            while (b < N && A[b]-A[a] <= mid) b++;
            num++, n = b;
            if (A[N-1]-A[n-1] <= mid) break;
        }
        if (num <= K) high = mid;
        else low = mid;
    }
    cout << high << '\n';
    long long n = 0;
    while (n < N && A[n] <= high) n++;
    bs[n-1] = 1;
    while (n < N) {
        long long a = n;
        while (a < N && A[a]-A[n-1] <= high) a++;
        long long b = a;
        while (b < N && A[b]-A[a] <= high) b++;
        bs[b-1] = 1, n = b;
        if (A[N-1]-A[n-1] <= high) break;
    }
    for (long long i = 0; i < N && bs.count() < K; ++i) if (!bs[i]) bs[i] = 1;
    for (long long i = 0; i < N; ++i) if (bs[i]) cout << i+1 << ' ';

    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:43:47: warning: comparison of integer expressions of different signedness: 'std::size_t' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   43 |     for (long long i = 0; i < N && bs.count() < K; ++i) if (!bs[i]) bs[i] = 1;
      |                                    ~~~~~~~~~~~^~~

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