oj.uz

Submission #223939

# Submission time Handle Problem Language Result Execution time Memory
223939 2020-04-16T22:06:14 Z NaimSS Museum (CEOI17_museum) C++14
0 / 100
 532 ms 1048580 KB 
#include <bits/stdc++.h>
//#define int long long
#define ld long double
#define endl "\n"
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define pb(x) push_back(x)
#define mp(a,b) make_pair(a,b)
#define ms(v,x) memset(v,x,sizeof(v))
#define ff first
#define ss second
#define rep(i,l,r) for(int i = (int)l;i<(int)r;i++)
#define td(v) v.begin(),v.end()
//#define M   1000000007 // 1e9 + 7
#define MAXN 200100
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
inline int mod(int n, int m){ int ret = n%m; if(ret < 0) ret += m; return ret; }
int gcd(int a, int b){return (b == 0 ? a : gcd(b, a%b));}
int exp(int a,int b,int m){
    
    if(b==0) return 1;
    if(b==1) return mod(a,m);
    int k = mod(exp(a,b/2,m),m);
    if(b&1){
        return mod(a*mod(k*k,m),m);
    }
    else return mod(k*k,m);
}

int n,k,x;
const int N = 1e4 + 100;
vector<pii> g[N];
int sz[N];
int dp[N][N][3];

int aux[N][3];
int vis[N];
void solve(int v,int p=-1,int ar=0){
    if(vis[v])return;
    vis[v] = 1;

    

    sz[v] = 1;
    dp[v][1][0] = ar;
    dp[v][1][1] = 2*ar;
    dp[v][1][2] = ar;

    for(auto nx : g[v]){
        int to = nx.ff;
        if(to==p)continue;
        solve(to,v,nx.ss);

        for(int i=0;i<=sz[v]+sz[to];i++){
            aux[i][0] = aux[i][1] = aux[i][2] = 1e9;
            
        }

        for(int i=1;i<=sz[v];i++){
            for(int j=1;j<=sz[to];j++){
                aux[i+j][1] = min(aux[i+j][1],dp[v][i][1] + dp[to][j][1]);                
                aux[i+j][0] = min(aux[i+j][0], dp[v][i][0] + dp[to][j][1]);
                aux[i+j][2] = min(aux[i+j][2],dp[v][i][0] + dp[to][j][2]);
              
            }
        }
     

        for(int i=0;i<=sz[v]+sz[to];i++){
          
            dp[v][i][1] = min(dp[v][i][1],aux[i][1]);
            dp[v][i][0] = min(dp[v][i][0],aux[i][0]);
            dp[v][i][2] = min(dp[v][i][2],aux[i][2]);
        }

        sz[v]+=sz[to];


    }


}

int32_t main(){
    rep(i,0,N)rep(j,0,N)dp[i][j][0] = dp[i][j][1] = dp[i][j][2] = 1e9;
    fastio;
    cin>>n>>k>>x;
    for(int i=0;i<n-1;i++){
        int a,b,c;
        cin>>a>>b>>c;
        g[a].pb(pii(b,c));
        g[b].pb(pii(a,c));
    }

    solve(x);

    cout<<dp[x][k][2]<<endl;

}

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 532 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 528 ms 1048576 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 35.0

# Verdict Execution time Memory Grader output
1 Runtime error 528 ms 1048576 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 532 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -