oj.uz

Submission #541276

# Submission time Handle Problem Language Result Execution time Memory
541276 2022-03-22T21:34:32 Z Victor Parkovi (COCI22_parkovi) C++17
40 / 110
 3000 ms 49104 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];
uset<ll> ans;

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.insert(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.insert(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;
}

ll dists[200005];
void dfs2(int u, int p) {
    if (ans.count(u)) dists[u] = 0;
    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);
            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));
        dfs2(0,0);
        dfs3(0,0);

        ll max_dist = 0;
        rep(i, 0, n) {
            max_dist = max(max_dist, dists[i]);
        }

        if (max_dist > mid) ans.insert(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(val, ans) ans.insert(val);
    dfs2(0,0);
    dfs3(0,0);

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

    if (max_dist > mid) ans.insert(0);

    rep(i, 0, n) {
        if (sz(ans) == k) break;
        ans.insert(i);
    }

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

Compilation message

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

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 6612 KB Output is correct
2 Correct 7 ms 6484 KB Output is correct
3 Correct 7 ms 6484 KB Output is correct
4 Correct 7 ms 6612 KB Output is correct
5 Correct 7 ms 6484 KB Output is correct
6 Correct 7 ms 6612 KB Output is correct
7 Correct 7 ms 6604 KB Output is correct
8 Correct 7 ms 6484 KB Output is correct
9 Correct 7 ms 6612 KB Output is correct
10 Correct 8 ms 6528 KB Output is correct
11 Correct 7 ms 6612 KB Output is correct
12 Correct 7 ms 6484 KB Output is correct
13 Correct 7 ms 6484 KB Output is correct
14 Correct 7 ms 6612 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 783 ms 37400 KB Output is correct
2 Correct 808 ms 38324 KB Output is correct
3 Correct 801 ms 20960 KB Output is correct
4 Execution timed out 3088 ms 20988 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 835 ms 38840 KB Output is correct
2 Correct 842 ms 37904 KB Output is correct
3 Correct 740 ms 36324 KB Output is correct
4 Correct 751 ms 36244 KB Output is correct
5 Correct 1209 ms 47148 KB Output is correct
6 Correct 1212 ms 42892 KB Output is correct
7 Correct 1320 ms 45764 KB Output is correct
8 Correct 847 ms 39424 KB Output is correct
9 Correct 847 ms 39096 KB Output is correct
10 Correct 811 ms 38500 KB Output is correct
11 Correct 798 ms 37264 KB Output is correct
12 Correct 1301 ms 49104 KB Output is correct
13 Correct 1341 ms 46224 KB Output is correct
14 Correct 1282 ms 43608 KB Output is correct
15 Correct 811 ms 38372 KB Output is correct
16 Correct 776 ms 37056 KB Output is correct
17 Correct 755 ms 36960 KB Output is correct
18 Correct 802 ms 38520 KB Output is correct
19 Correct 861 ms 46288 KB Output is correct
20 Correct 876 ms 45188 KB Output is correct
21 Correct 884 ms 43332 KB Output is correct

Subtask #4
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 6612 KB Output is correct
2 Correct 7 ms 6484 KB Output is correct
3 Correct 7 ms 6484 KB Output is correct
4 Correct 7 ms 6612 KB Output is correct
5 Correct 7 ms 6484 KB Output is correct
6 Correct 7 ms 6612 KB Output is correct
7 Correct 7 ms 6604 KB Output is correct
8 Correct 7 ms 6484 KB Output is correct
9 Correct 7 ms 6612 KB Output is correct
10 Correct 8 ms 6528 KB Output is correct
11 Correct 7 ms 6612 KB Output is correct
12 Correct 7 ms 6484 KB Output is correct
13 Correct 7 ms 6484 KB Output is correct
14 Correct 7 ms 6612 KB Output is correct
15 Correct 783 ms 37400 KB Output is correct
16 Correct 808 ms 38324 KB Output is correct
17 Correct 801 ms 20960 KB Output is correct
18 Execution timed out 3088 ms 20988 KB Time limit exceeded
19 Halted 0 ms 0 KB -