oj.uz

Submission #556131

# Submission time Handle Problem Language Result Execution time Memory
556131 2022-05-02T12:34:57 Z new_acc Parkovi (COCI22_parkovi) C++14
110 / 110
 2199 ms 92608 KB 
#include<bits/stdc++.h>
#define fi first
#define se second
#define pitem item*
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<ll> vl;
const int N=1e6+10;
const int SS=1<<19;
const int INFi=2e9;
const ll INFl=1e15;
const ll mod2=998244353;
const ll mod=1e9+7;
const ll mod3=1000696969;
const ll p=70032301;
const ull p2=913;
const int L=20;
struct st{
    int a;
    ll b,c;
};
int n,k;
vector<pair<int,int> >graf[N];
bool stw[N];
st dp[N];
void dfs(int v,int o,ll x){
    vi v1,v2,v3;
    for(auto [u,c]:graf[v]){
        if(u==o) continue;
        dfs(u,v,x);
    }
    if(graf[v].size()==1 and v!=o){
        stw[v]=1;
        dp[v]={1,0,0};
        return;
    }
    ll mini=INFl,mini2=INFl;
    int g=0,g2=0;
    for(auto [u,c]:graf[v]){
        if(u==o) continue;
        if(dp[u].b==0 and dp[u].c+(ll)c>x and mini>=dp[u].b+(ll)c) mini=dp[u].b+(ll)c,g=u;
    }
    for(auto [u,c]:graf[v]){
        if(u==o) continue;
        if(dp[u].b!=0 and mini2>=dp[u].b+(ll)c) mini2=dp[u].b+(ll)c,g2=u;
    }
    st res1={0,mini2,0};
    if(mini2>x)res1.a=INFi;
    else{
        for(auto [u,c]:graf[v]){
            if(u==o) continue;
            if(u==g2){
                res1.a+=dp[u].a;
                continue;
            }
            if(dp[u].b==0 and dp[u].c+(ll)c+mini2<=x) res1.a--,v1.push_back(u);
            else res1.b=min(res1.b,dp[u].b+(ll)c);
            res1.a+=dp[u].a;
        }
    }
    st res3={0,mini,0};
    if(mini>x) res3.a=INFi;
    else{
        for(auto [u,c]:graf[v]){
            if(u==o) continue;
            if(u==g){
                res3.a+=dp[u].a;
                continue;
            }
            if(dp[u].b==0 and dp[u].c+(ll)c+mini<=x) res3.a--,v3.push_back(u);
            else res3.b=min(res3.b,dp[u].b+(ll)c);
            res3.a+=dp[u].a;
        }
    }
    if(res1.a==res3.a){
        if(res3.b<res1.b) swap(res3,res1),swap(v1,v3);
    }else{
        if(res3.a<res1.a) swap(res3,res1),swap(v1,v3);
    }
    st res2={1,0,0};
    for(auto [u,c]:graf[v]){
        if(u==o) continue;
        if(dp[u].b==0 and dp[u].c+(ll)c<=x) res2.a--,res2.c=max(res2.c,(ll)c+dp[u].c),v2.push_back(u);
        res2.a+=dp[u].a;
    }
    if(res2.a<=res1.a){
        dp[v]=res2;
        stw[v]=1;
        for(auto u:v2) stw[u]=0;
    }else{
        dp[v]=res1;
        for(auto u:v1) stw[u]=0;
    }
}
bool check(ll x){
    for(int i=1;i<=n;i++) stw[i]=0;
    dfs(1,1,x);
    return dp[1].a<=k;
}
ll bs(ll pocz,ll kon){
    ll res,sr;
    while(pocz<=kon){
        sr=(pocz+kon)>>1LL;
        if(check(sr)) res=sr,kon=sr-1;
        else pocz=sr+1;
    }
    return res;
}
void solve(){
    cin>>n>>k;
    for(int a,b,c,i=1;i<n;i++){
        cin>>a>>b>>c;
        graf[a].push_back({b,c}),graf[b].push_back({a,c});
    }
    if(n==1){
        cout<<0<<"\n";
        return;
    }
    ll res=bs(0,(ll)1e15);
    check(res);
    cout<<res<<"\n";
    vi ans;
    for(int i=1;i<=n;i++) if(stw[i]) ans.push_back(i);
    for(int i=1;i<=n;i++) if(!stw[i] and ans.size()<k) ans.push_back(i);
    sort(ans.begin(),ans.end());
    for(auto u:ans) cout<<u<<" ";
    cout<<"\n";
}
int main(){
    ios_base::sync_with_stdio(0),cin.tie(0);
    int tt=1;
    while(tt--) solve();
}

Compilation message

Main.cpp: In function 'void dfs(int, int, ll)':
Main.cpp:30:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   30 |     for(auto [u,c]:graf[v]){
      |              ^
Main.cpp:41:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   41 |     for(auto [u,c]:graf[v]){
      |              ^
Main.cpp:45:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   45 |     for(auto [u,c]:graf[v]){
      |              ^
Main.cpp:52:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   52 |         for(auto [u,c]:graf[v]){
      |                  ^
Main.cpp:66:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   66 |         for(auto [u,c]:graf[v]){
      |                  ^
Main.cpp:83:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   83 |     for(auto [u,c]:graf[v]){
      |              ^
Main.cpp: In function 'void solve()':
Main.cpp:126:52: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  126 |     for(int i=1;i<=n;i++) if(!stw[i] and ans.size()<k) ans.push_back(i);
      |                                          ~~~~~~~~~~^~
Main.cpp: In function 'll bs(ll, ll)':
Main.cpp:109:12: warning: 'res' may be used uninitialized in this function [-Wmaybe-uninitialized]
  109 |     return res;
      |            ^~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23764 KB Output is correct
2 Correct 13 ms 23924 KB Output is correct
3 Correct 12 ms 23816 KB Output is correct
4 Correct 12 ms 23764 KB Output is correct
5 Correct 12 ms 23764 KB Output is correct
6 Correct 12 ms 23812 KB Output is correct
7 Correct 12 ms 23720 KB Output is correct
8 Correct 12 ms 23816 KB Output is correct
9 Correct 12 ms 23820 KB Output is correct
10 Correct 12 ms 23824 KB Output is correct
11 Correct 12 ms 23764 KB Output is correct
12 Correct 13 ms 23700 KB Output is correct
13 Correct 12 ms 23764 KB Output is correct
14 Correct 12 ms 23764 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1163 ms 86988 KB Output is correct
2 Correct 1164 ms 90084 KB Output is correct
3 Correct 702 ms 42980 KB Output is correct
4 Correct 1897 ms 39560 KB Output is correct
5 Correct 1901 ms 39048 KB Output is correct
6 Correct 1959 ms 39068 KB Output is correct
7 Correct 1857 ms 37876 KB Output is correct
8 Correct 1997 ms 38632 KB Output is correct
9 Correct 1980 ms 39044 KB Output is correct
10 Correct 2089 ms 39320 KB Output is correct
11 Correct 1489 ms 44024 KB Output is correct
12 Correct 1462 ms 45060 KB Output is correct
13 Correct 1557 ms 47068 KB Output is correct
14 Correct 1456 ms 43348 KB Output is correct
15 Correct 1465 ms 41972 KB Output is correct
16 Correct 1453 ms 44544 KB Output is correct
17 Correct 1422 ms 42592 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1145 ms 91288 KB Output is correct
2 Correct 1082 ms 89404 KB Output is correct
3 Correct 1056 ms 86036 KB Output is correct
4 Correct 1042 ms 85780 KB Output is correct
5 Correct 1051 ms 90220 KB Output is correct
6 Correct 1171 ms 90004 KB Output is correct
7 Correct 1136 ms 92248 KB Output is correct
8 Correct 1098 ms 91148 KB Output is correct
9 Correct 1154 ms 90440 KB Output is correct
10 Correct 1109 ms 89096 KB Output is correct
11 Correct 1112 ms 86676 KB Output is correct
12 Correct 1193 ms 91904 KB Output is correct
13 Correct 1231 ms 92608 KB Output is correct
14 Correct 1153 ms 91172 KB Output is correct
15 Correct 1147 ms 88328 KB Output is correct
16 Correct 1066 ms 85636 KB Output is correct
17 Correct 1071 ms 85488 KB Output is correct
18 Correct 1138 ms 88828 KB Output is correct
19 Correct 1086 ms 87056 KB Output is correct
20 Correct 1191 ms 88932 KB Output is correct
21 Correct 1132 ms 87564 KB Output is correct

Subtask #4
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23764 KB Output is correct
2 Correct 13 ms 23924 KB Output is correct
3 Correct 12 ms 23816 KB Output is correct
4 Correct 12 ms 23764 KB Output is correct
5 Correct 12 ms 23764 KB Output is correct
6 Correct 12 ms 23812 KB Output is correct
7 Correct 12 ms 23720 KB Output is correct
8 Correct 12 ms 23816 KB Output is correct
9 Correct 12 ms 23820 KB Output is correct
10 Correct 12 ms 23824 KB Output is correct
11 Correct 12 ms 23764 KB Output is correct
12 Correct 13 ms 23700 KB Output is correct
13 Correct 12 ms 23764 KB Output is correct
14 Correct 12 ms 23764 KB Output is correct
15 Correct 1163 ms 86988 KB Output is correct
16 Correct 1164 ms 90084 KB Output is correct
17 Correct 702 ms 42980 KB Output is correct
18 Correct 1897 ms 39560 KB Output is correct
19 Correct 1901 ms 39048 KB Output is correct
20 Correct 1959 ms 39068 KB Output is correct
21 Correct 1857 ms 37876 KB Output is correct
22 Correct 1997 ms 38632 KB Output is correct
23 Correct 1980 ms 39044 KB Output is correct
24 Correct 2089 ms 39320 KB Output is correct
25 Correct 1489 ms 44024 KB Output is correct
26 Correct 1462 ms 45060 KB Output is correct
27 Correct 1557 ms 47068 KB Output is correct
28 Correct 1456 ms 43348 KB Output is correct
29 Correct 1465 ms 41972 KB Output is correct
30 Correct 1453 ms 44544 KB Output is correct
31 Correct 1422 ms 42592 KB Output is correct
32 Correct 1145 ms 91288 KB Output is correct
33 Correct 1082 ms 89404 KB Output is correct
34 Correct 1056 ms 86036 KB Output is correct
35 Correct 1042 ms 85780 KB Output is correct
36 Correct 1051 ms 90220 KB Output is correct
37 Correct 1171 ms 90004 KB Output is correct
38 Correct 1136 ms 92248 KB Output is correct
39 Correct 1098 ms 91148 KB Output is correct
40 Correct 1154 ms 90440 KB Output is correct
41 Correct 1109 ms 89096 KB Output is correct
42 Correct 1112 ms 86676 KB Output is correct
43 Correct 1193 ms 91904 KB Output is correct
44 Correct 1231 ms 92608 KB Output is correct
45 Correct 1153 ms 91172 KB Output is correct
46 Correct 1147 ms 88328 KB Output is correct
47 Correct 1066 ms 85636 KB Output is correct
48 Correct 1071 ms 85488 KB Output is correct
49 Correct 1138 ms 88828 KB Output is correct
50 Correct 1086 ms 87056 KB Output is correct
51 Correct 1191 ms 88932 KB Output is correct
52 Correct 1132 ms 87564 KB Output is correct
53 Correct 2032 ms 39424 KB Output is correct
54 Correct 2021 ms 39880 KB Output is correct
55 Correct 2199 ms 40588 KB Output is correct
56 Correct 2170 ms 40268 KB Output is correct
57 Correct 2037 ms 40928 KB Output is correct
58 Correct 1953 ms 39648 KB Output is correct
59 Correct 1867 ms 42228 KB Output is correct
60 Correct 2137 ms 39120 KB Output is correct
61 Correct 1821 ms 37736 KB Output is correct
62 Correct 1879 ms 38680 KB Output is correct
63 Correct 2117 ms 39308 KB Output is correct
64 Correct 1916 ms 40348 KB Output is correct
65 Correct 2037 ms 39468 KB Output is correct
66 Correct 1878 ms 39868 KB Output is correct
67 Correct 1847 ms 38532 KB Output is correct
68 Correct 2033 ms 41700 KB Output is correct
69 Correct 1099 ms 89920 KB Output is correct
70 Correct 1078 ms 85908 KB Output is correct
71 Correct 1200 ms 92324 KB Output is correct
72 Correct 648 ms 41916 KB Output is correct
73 Correct 652 ms 41192 KB Output is correct
74 Correct 685 ms 41196 KB Output is correct
75 Correct 1382 ms 45780 KB Output is correct
76 Correct 1540 ms 44776 KB Output is correct
77 Correct 1406 ms 44664 KB Output is correct
78 Correct 1435 ms 44536 KB Output is correct