oj.uz

Submission #541271

# Submission time Handle Problem Language Result Execution time Memory
541271 2022-03-22T21:11:00 Z Victor Parkovi (COCI22_parkovi) C++17
10 / 110
 3000 ms 51208 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];
vll solution;
ll mid, max_dist[200005], to_park[200005], need[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;
                solution.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];
        solution.pb(u);
    }

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

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

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));
        set<pll>pq;
        trav(val, solution) pq.emplace(0,val), dists[val]=0;

        while(!pq.empty()) {
            ll u,d;
            tie(d,u)=*pq.begin();
            pq.erase(pq.begin());

            trav(edge,graph[u]) {
                ll v,w;
                tie(v,w)=edge;
                if(d+w>=dists[v]) continue;

                pq.erase({dists[v],v});
                dists[v]=d+w;
                pq.insert({dists[v],v});
            }
        }

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

        if (max_dist > mid) solution.pb(0);

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

    mid = lo;
    dfs(0, 0);
    fill(dists, dists + 200005, ll(1e16));
    set<ll> ans;
    trav(val, solution) ans.insert(val), dfs2(val, val, 0);

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

    if (max_dist > mid) solution.pb(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:26: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  130 |         if (sz(solution) <= k)
      |                          ^
Main.cpp:152:21: warning: comparison of integer expressions of different signedness: 'std::set<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  152 |         if (sz(ans) == k) break;
      |                     ^

Subtask #1
10.0 / 10.0

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

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 952 ms 37400 KB Output is correct
2 Correct 962 ms 38244 KB Output is correct
3 Execution timed out 3060 ms 32932 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1958 ms 38804 KB Output is correct
2 Correct 1954 ms 37908 KB Output is correct
3 Correct 992 ms 36428 KB Output is correct
4 Correct 860 ms 36320 KB Output is correct
5 Execution timed out 3077 ms 51208 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 6484 KB Output is correct
2 Correct 9 ms 6484 KB Output is correct
3 Correct 9 ms 6484 KB Output is correct
4 Correct 9 ms 6608 KB Output is correct
5 Correct 9 ms 6608 KB Output is correct
6 Correct 9 ms 6608 KB Output is correct
7 Correct 9 ms 6612 KB Output is correct
8 Correct 10 ms 6612 KB Output is correct
9 Correct 11 ms 6612 KB Output is correct
10 Correct 9 ms 6612 KB Output is correct
11 Correct 9 ms 6612 KB Output is correct
12 Correct 10 ms 6612 KB Output is correct
13 Correct 9 ms 6612 KB Output is correct
14 Correct 9 ms 6484 KB Output is correct
15 Correct 952 ms 37400 KB Output is correct
16 Correct 962 ms 38244 KB Output is correct
17 Execution timed out 3060 ms 32932 KB Time limit exceeded
18 Halted 0 ms 0 KB -