oj.uz

답안 #543529

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
543529 2022-03-30T20:47:30 Z Victor Parkovi (COCI22_parkovi) C++17
40 / 110
 3000 ms 41724 KB 
// #pragma GCC target ("avx,avx2,fma")
// #pragma GCC optimize ("Ofast,inline") // O1 - O2 - O3 - Os - Ofast
// #pragma GCC optimize ("unroll-loops")
#include <bits/stdc++.h>

using namespace std;

#define rep(i, a, b) for (int i = (a); i < (b); ++i)
#define per(i, a, b) for (int i = (b - 1); i >= (a); --i)
#define trav(a, x) for (auto &a : x)

#define all(x) x.begin(), x.end()
#define sz(x) x.size()
#define pb push_back
#define debug(x) cout << #x << " = " << x << endl

#define umap unordered_map
#define uset unordered_set

typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;

typedef long long ll;
typedef pair<ll, ll> pll;
typedef vector<ll> vll;
typedef vector<pll> vpll;

const int INF = 1'000'000'007;

int k, n;
vpll graph[200005];
ll mid, max_dist[200005], to_park[200005], need[200005];
vll ans;

ll all_max_dist = 0;
ll dists[200005];

void dfs(ll u, ll p) {
    max_dist[u] = 0;
    to_park[u] = ll(1e16);
    need[u] = 0;

    trav(edge, graph[u]) {
        ll v, w;
        tie(v, w) = edge;
        if (v != p) {
            dfs(v, u);

            need[u] += need[v];

            max_dist[v] += w;
            to_park[v] += w;

            if (max_dist[v] > mid) {
                max_dist[v] = -1e16;
                to_park[v] = w;
                ++need[u];
                // cout << "u = " << u + 1 << " v = " << v + 1 << endl;
                ans.pb(v);
            }

            // cout<<max_dist[u]<<" "<<to_park[u]<<" "<<max_dist[v]<<" "<<to_park[v]<<endl;
            if (max_dist[u] + to_park[v] <= mid) max_dist[u] = ll(-1e16);
            if (max_dist[v] + to_park[u] > mid && max_dist[v] > max_dist[u]) max_dist[u] = max_dist[v];
            if (to_park[v] < to_park[u]) to_park[u] = to_park[v];
        }
    }

    if (!u && to_park[u] > mid) {
        ++need[u];
        ans.pb(u);
    }

    // cout << "u = " << u + 1 << " p = " << p + 1 << " max_dist = " << max_dist[u] << " to_park = " << to_park[u] << endl;
    // cout << "ans = " << need[u] << endl << endl;
}

void dfs2(int u, int p) {
    trav(edge, graph[u]) {
        ll v, w;
        tie(v, w) = edge;
        if (v != p) {
            dfs2(v, u);
            dists[u] = min(dists[u], dists[v] + w);
        }
    }
}

void dfs3(int u, int p) {
    trav(edge, graph[u]) {
        ll v, w;
        tie(v, w) = edge;
        if (v != p) {
            dists[v] = min(dists[v], dists[u] + w);
            all_max_dist=max(all_max_dist,dists[v]);
            dfs3(v, u);
        }
    }
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin.exceptions(cin.failbit);

    cin >> n >> k;
    rep(i, 1, n) {
        int u, v, w;
        cin >> u >> v >> w;
        graph[--u].emplace_back(--v, w);
        graph[v].emplace_back(u, w);
    }

    ll lo = 0, hi = ll(1e15);
    while (lo != hi) {
        mid = (lo + hi) / 2;
        dfs(0, 0);

        fill(dists, dists + 200005, ll(1e15));
        trav(node, ans) dists[node] = 0;
        all_max_dist=0;
        dfs2(0, 0);
        dfs3(0, 0);

        if (all_max_dist > mid) ans.pb(0);

        if (sz(ans) <= k)
            hi = mid;
        else
            lo = mid + 1;
        // debug(sz(ans));
        // cout << endl;
        ans.clear();
    }

    mid = lo;
    dfs(0, 0);
    fill(dists, dists + 200005, ll(1e16));
    trav(node, ans) dists[node] = 0;
    dfs2(0, 0);
    dfs3(0, 0);

    all_max_dist = 0;
    rep(i, 0, n) all_max_dist = max(all_max_dist, dists[i]);
    // debug(all_max_dist);

    if (all_max_dist > mid) {
        ans.pb(0);
        dists[0] = 0;
    }

    rep(i, 0, n) {
        if (sz(ans) == k) break;
        if (dists[i]) ans.pb(i);
    }

    cout << mid << endl;
    trav(val, ans) cout << val + 1 << ' ';
    cout << endl;
    return 0;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:129:21: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  129 |         if (sz(ans) <= k)
      |                     ^
Main.cpp:155:21: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  155 |         if (sz(ans) == k) break;
      |                     ^

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 6484 KB Output is correct
2 Correct 7 ms 6580 KB Output is correct
3 Correct 9 ms 6612 KB Output is correct
4 Correct 8 ms 6612 KB Output is correct
5 Correct 9 ms 6612 KB Output is correct
6 Correct 8 ms 6612 KB Output is correct
7 Correct 10 ms 6612 KB Output is correct
8 Correct 7 ms 6516 KB Output is correct
9 Correct 7 ms 6612 KB Output is correct
10 Correct 6 ms 6612 KB Output is correct
11 Correct 7 ms 6612 KB Output is correct
12 Correct 7 ms 6580 KB Output is correct
13 Correct 7 ms 6584 KB Output is correct
14 Correct 7 ms 6484 KB Output is correct

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 830 ms 37748 KB Output is correct
2 Correct 908 ms 38584 KB Output is correct
3 Correct 926 ms 21144 KB Output is correct
4 Execution timed out 3044 ms 20932 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 903 ms 39144 KB Output is correct
2 Correct 828 ms 38248 KB Output is correct
3 Correct 769 ms 36580 KB Output is correct
4 Correct 783 ms 36584 KB Output is correct
5 Correct 893 ms 40520 KB Output is correct
6 Correct 972 ms 39540 KB Output is correct
7 Correct 922 ms 41152 KB Output is correct
8 Correct 889 ms 39352 KB Output is correct
9 Correct 860 ms 39068 KB Output is correct
10 Correct 858 ms 38468 KB Output is correct
11 Correct 809 ms 37248 KB Output is correct
12 Correct 935 ms 41724 KB Output is correct
13 Correct 961 ms 41636 KB Output is correct
14 Correct 909 ms 40200 KB Output is correct
15 Correct 853 ms 38388 KB Output is correct
16 Correct 794 ms 37196 KB Output is correct
17 Correct 822 ms 37068 KB Output is correct
18 Correct 835 ms 38644 KB Output is correct
19 Correct 819 ms 39472 KB Output is correct
20 Correct 854 ms 40204 KB Output is correct
21 Correct 824 ms 39124 KB Output is correct

Subtask #4
0 / 60.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 6484 KB Output is correct
2 Correct 7 ms 6580 KB Output is correct
3 Correct 9 ms 6612 KB Output is correct
4 Correct 8 ms 6612 KB Output is correct
5 Correct 9 ms 6612 KB Output is correct
6 Correct 8 ms 6612 KB Output is correct
7 Correct 10 ms 6612 KB Output is correct
8 Correct 7 ms 6516 KB Output is correct
9 Correct 7 ms 6612 KB Output is correct
10 Correct 6 ms 6612 KB Output is correct
11 Correct 7 ms 6612 KB Output is correct
12 Correct 7 ms 6580 KB Output is correct
13 Correct 7 ms 6584 KB Output is correct
14 Correct 7 ms 6484 KB Output is correct
15 Correct 830 ms 37748 KB Output is correct
16 Correct 908 ms 38584 KB Output is correct
17 Correct 926 ms 21144 KB Output is correct
18 Execution timed out 3044 ms 20932 KB Time limit exceeded
19 Halted 0 ms 0 KB -