oj.uz

답안 #884920

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
884920 2023-12-08T16:51:33 Z HossamHero7 Parkovi (COCI22_parkovi) C++14
30 / 110
 1769 ms 43528 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
const int N = 2e5 + 5;
vector<pair<int,ll>> adj[N];
pair<int,ll> P[N];
vector<pair<int,int>> leaves;
void dfs(int node,int par,int dep){
    if(adj[node].size() == 1 && node != 1) leaves.push_back({dep,node});
    for(auto [ch,c] : adj[node]){
        if(ch == par) continue;
        P[ch] = {node,c};
        dfs(ch,node,dep+1);
    }
}
void solve(){
    int n,k;
    cin>>n>>k;
    for(int i=0;i<n-1;i++){
        int a,b,c;
        cin>>a>>b>>c;
        adj[a].push_back({b,c});
        adj[b].push_back({a,c});
    }
    dfs(1,0,0);
    ll l = 1;
    ll r = 1e18;
    ll ans = 0;
    vector<int> v;
    while(l <= r){
        ll md = l + r >> 1;
        priority_queue<pair<int,int>> q;
        vector<bool> vis(n+1);
        for(auto i : leaves) q.push(i) , vis[i.second] = 1;
        vector<ll> cost(n+1);
        vector<ll> covered(n+1,1e18);
        vector<int> tmp;
        while(q.size()){
            auto [dep,node] = q.top();       q.pop();
            auto [par,c] = P[node];
            if(covered[node] <= md){
                //cout<<"A "<<node<<' '<<covered[node]<<' '<<cost[node]<<endl;
                covered[par] = min(covered[par] , covered[node] + c);
                if(!vis[par] && par) q.push({dep-1,par}) , vis[par] = 1;
            }
            else {
                if(covered[par] <= md){
                    if(covered[par] + cost[node] + c <= md) {
                        if(!vis[par] && par) q.push({dep-1,par}) , vis[par] = 1;
                    }
                    else {
                        tmp.push_back(node);
                        if(!vis[par] && par) q.push({dep-1,par}) , vis[par] = 1;
                    }
                }
                else {
                    if(cost[node] + c <= md){
                        //cout<<"B1 "<<node<<' '<<covered[node]<<' '<<cost[node]<<endl;
                        cost[par] = max(cost[par],cost[node] + c);
                        if(!vis[par] && par) q.push({dep-1,par}) , vis[par] = 1;
                    }
                    else {
                        tmp.push_back(node);
                        covered[par] = min(covered[par] , c);
                        if(!vis[par] && par) q.push({dep-1,par}) , vis[par] = 1;
                    }
                }
            }
        }
        if((tmp.empty() || tmp.back() != 1) && covered[1] > md) tmp.push_back(1);
        if(tmp.size() <= k){
            ans = md;
            v = tmp;
            r = md - 1;
        }
        else l = md + 1;
    }
    cout<<ans<<endl;
    vector<bool> vis(n+1);
    for(auto i : v) vis[i] = 1;
    for(int i=1;i<=n&&v.size()!=k;i++){
        if(!vis[i]) v.push_back(i);
    }
    for(auto i : v) cout<<i<<' ';
    cout<<endl;
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);      cout.tie(0);
    int t=1;
    //cin>>t;
    while(t--){
        solve();
    }
    return 0;
}

Compilation message

Main.cpp: In function 'void dfs(int, int, int)':
Main.cpp:11:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   11 |     for(auto [ch,c] : adj[node]){
      |              ^
Main.cpp: In function 'void solve()':
Main.cpp:32:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   32 |         ll md = l + r >> 1;
      |                 ~~^~~
Main.cpp:40:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   40 |             auto [dep,node] = q.top();       q.pop();
      |                  ^
Main.cpp:41:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   41 |             auto [par,c] = P[node];
      |                  ^
Main.cpp:72:23: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   72 |         if(tmp.size() <= k){
      |            ~~~~~~~~~~~^~~~
Main.cpp:82:31: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   82 |     for(int i=1;i<=n&&v.size()!=k;i++){
      |                       ~~~~~~~~^~~

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 5980 KB Output is correct
2 Correct 2 ms 6056 KB Output is correct
3 Correct 2 ms 5980 KB Output is correct
4 Correct 2 ms 5980 KB Output is correct
5 Correct 2 ms 5980 KB Output is correct
6 Correct 2 ms 5980 KB Output is correct
7 Incorrect 2 ms 5980 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 337 ms 37540 KB Output is correct
2 Correct 338 ms 39736 KB Output is correct
3 Correct 1551 ms 30320 KB Output is correct
4 Incorrect 1769 ms 27568 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 349 ms 40264 KB Output is correct
2 Correct 333 ms 39380 KB Output is correct
3 Correct 317 ms 37856 KB Output is correct
4 Correct 311 ms 37708 KB Output is correct
5 Correct 358 ms 43528 KB Output is correct
6 Correct 353 ms 41484 KB Output is correct
7 Correct 366 ms 42960 KB Output is correct
8 Correct 345 ms 39840 KB Output is correct
9 Correct 357 ms 39536 KB Output is correct
10 Correct 333 ms 38892 KB Output is correct
11 Correct 318 ms 37768 KB Output is correct
12 Correct 375 ms 42816 KB Output is correct
13 Correct 372 ms 43136 KB Output is correct
14 Correct 366 ms 41444 KB Output is correct
15 Correct 347 ms 38168 KB Output is correct
16 Correct 331 ms 36904 KB Output is correct
17 Correct 331 ms 36804 KB Output is correct
18 Correct 347 ms 38580 KB Output is correct
19 Correct 345 ms 39020 KB Output is correct
20 Correct 350 ms 40844 KB Output is correct
21 Correct 344 ms 39852 KB Output is correct

Subtask #4
0 / 60.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 5980 KB Output is correct
2 Correct 2 ms 6056 KB Output is correct
3 Correct 2 ms 5980 KB Output is correct
4 Correct 2 ms 5980 KB Output is correct
5 Correct 2 ms 5980 KB Output is correct
6 Correct 2 ms 5980 KB Output is correct
7 Incorrect 2 ms 5980 KB Output isn't correct
8 Halted 0 ms 0 KB -