oj.uz

Submission #223956

# Submission time Handle Problem Language Result Execution time Memory
223956 2020-04-16T22:31:29 Z NaimSS Museum (CEOI17_museum) C++14
20 / 100
 165 ms 13048 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];
const int MAXK = 100;
int dp[N][MAXK][3];
int aux[N][3];
int vis[N];
void solve(int v,int p=-1,int ar=0){
    if(vis[v]==1LL)return;
    vis[v] = 1LL;

    

    sz[v] = 1;
    dp[v][0][0] = 0;
    dp[v][1][0] = 2*ar; // sobe
    dp[v][1][1] = ar; // fica mas nao escolhi
    dp[v][1][2] = ar; // ja escolhi onde descer

    for(auto nx : g[v]){
        int to = nx.ff;
        if(to==p)continue;
        solve(to,v,nx.ss);
        rep(i,0,sz[v] + sz[to]+  1)aux[i][0]= aux[i][1] =aux[i][2] = 1e9;
       
        for(int i=1;i<=sz[v];i++){ 
            for(int j=0;j<=sz[to];j++){
          
                aux[i+j][0] = min(aux[i+j][0],dp[v][i][0] + dp[to][j][0]);
                // os dois sobem ^ 
                aux[i+j][1] = min(aux[i+j][1],dp[v][i][1] + dp[to][j][0]);
                // nao escolhi ^ 
                aux[i+j][2] = min(aux[i+j][2],dp[v][i][1] + dp[to][j][2]);
                // escolho descer em to ^
                aux[i+j][2] = min(aux[i+j][2],dp[v][i][2] + dp[to][j][0]);
                // ja escolhi e nao é em to ^
            }
        }
     

        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,MAXK)rep(xx,0,3){
        dp[i][j][xx] = 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<<min({dp[x][k][0],dp[x][k][1],dp[x][k][2]})<<endl;

}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 12416 KB Output is correct
2 Correct 11 ms 12416 KB Output is correct
3 Correct 11 ms 12416 KB Output is correct
4 Correct 11 ms 12416 KB Output is correct
5 Correct 10 ms 12416 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 165 ms 13048 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 35.0

# Verdict Execution time Memory Grader output
1 Incorrect 165 ms 13048 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 12416 KB Output is correct
2 Correct 11 ms 12416 KB Output is correct
3 Correct 11 ms 12416 KB Output is correct
4 Correct 11 ms 12416 KB Output is correct
5 Correct 10 ms 12416 KB Output is correct
6 Incorrect 165 ms 13048 KB Output isn't correct
7 Halted 0 ms 0 KB -