oj.uz

Submission #379527

# Submission time Handle Problem Language Result Execution time Memory
379527 2021-03-18T12:15:55 Z rrrr10000 Museum (CEOI17_museum) C++14
100 / 100
 648 ms 311916 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
typedef tuple<ll,ll,ll> PP;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef vector<bool> vb;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define REP(i,k,n) for(ll i=(ll)(k);i<(ll)(n);i++)
#define all(a) a.begin(),a.end()
#define fi first
#define se second
#define pb emplace_back
#define lb(v,k) (lower_bound(all(v),k)-v.begin())
template<class T> bool chmin(T&a,T b){if(a>b){a=b;return true;}return false;}
template<class T> bool chmax(T&a,T b){if(a<b){a=b;return true;}return false;}
template<class T> void out(T a){cout<<a<<'\n';}
template<class T> void outv(T v){rep(i,v.size()){if(i)cout<<' ';cout<<v[i];}cout<<'\n';}
template<class T> void outp(T p){cout<<'('<<p.fi<<','<<p.se<<')'<<endl;}
template<class T> void ouvp(T v){for(auto p:v)cout<<'('<<p.fi<<','<<p.se<<')';cout<<endl;}
template<class T> void outvv(T v){for(auto x:v)outv(x);}
const ll inf=1001001001001001001;
int main(){
    ll n,k,s;cin>>n>>k>>s;s--;
    vvp g(n);
    rep(i,n-1){
        ll a,b,c;cin>>a>>b>>c;
        a--;b--;
        g[a].pb(b,c);
        g[b].pb(a,c);
    }
    vvi dp0(n),dp1(n);
    vi dep(n);
    function<void(ll,ll)> dfs=[&](ll i,ll p){
        dp0[i].pb(0);dp1[i].pb(-dep[i]);
        for(auto x:g[i])if(x.fi!=p){
            dep[x.fi]=dep[i]+x.se;
            dfs(x.fi,i);
            rep(j,dp0[x.fi].size()){
                dp0[i].pb(inf);dp1[i].pb(inf);
            }
            for(int j=dp0[i].size()-1;j>=0;j--)if(dp0[i][j]!=inf){
                rep(k,dp0[x.fi].size()){
                    chmin(dp0[i][j+k+1],dp0[i][j]+dp0[x.fi][k]+x.se*2);
                    chmin(dp1[i][j+k+1],dp0[i][j]+dp1[x.fi][k]+x.se*2);
                    chmin(dp1[i][j+k+1],dp1[i][j]+dp0[x.fi][k]+x.se*2);
                }
            }
        }
    };dfs(s,-1);
    out(dp1[s][k-1]);
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 6508 KB Output is correct
2 Correct 157 ms 7148 KB Output is correct
3 Correct 648 ms 293356 KB Output is correct
4 Correct 308 ms 100460 KB Output is correct
5 Correct 191 ms 27756 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 6508 KB Output is correct
2 Correct 157 ms 7148 KB Output is correct
3 Correct 648 ms 293356 KB Output is correct
4 Correct 308 ms 100460 KB Output is correct
5 Correct 191 ms 27756 KB Output is correct
6 Correct 151 ms 4972 KB Output is correct
7 Correct 477 ms 181100 KB Output is correct
8 Correct 311 ms 2792 KB Output is correct
9 Correct 240 ms 3052 KB Output is correct
10 Correct 160 ms 4972 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 156 ms 6508 KB Output is correct
7 Correct 157 ms 7148 KB Output is correct
8 Correct 648 ms 293356 KB Output is correct
9 Correct 308 ms 100460 KB Output is correct
10 Correct 191 ms 27756 KB Output is correct
11 Correct 151 ms 4972 KB Output is correct
12 Correct 477 ms 181100 KB Output is correct
13 Correct 311 ms 2792 KB Output is correct
14 Correct 240 ms 3052 KB Output is correct
15 Correct 160 ms 4972 KB Output is correct
16 Correct 155 ms 8012 KB Output is correct
17 Correct 156 ms 7628 KB Output is correct
18 Correct 340 ms 120300 KB Output is correct
19 Correct 261 ms 2924 KB Output is correct
20 Correct 154 ms 5100 KB Output is correct
21 Correct 421 ms 175996 KB Output is correct
22 Correct 154 ms 7236 KB Output is correct
23 Correct 256 ms 3052 KB Output is correct
24 Correct 151 ms 4972 KB Output is correct
25 Correct 645 ms 311916 KB Output is correct