oj.uz

Submission #526730

# Submission time Handle Problem Language Result Execution time Memory
526730 2022-02-16T03:14:01 Z joelau Parkovi (COCI22_parkovi) C++14
0 / 110
 54 ms 5756 KB 
#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

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.0

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

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 42 ms 2024 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 1996 KB Output is correct
2 Correct 52 ms 5756 KB Output is correct
3 Correct 51 ms 5344 KB Output is correct
4 Incorrect 49 ms 5316 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 60.0

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