oj.uz

Submission #223965

# Submission time Handle Problem Language Result Execution time Memory
223965 2020-04-16T22:42:42 Z NaimSS Museum (CEOI17_museum) C++14
100 / 100
 637 ms 211320 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 + 2;
vector<pii> g[N];
int sz[N];
const int MAXK = 1e4 + 2;
vector<int> dp[N][3];
int aux[N][3];
int vis[N];
void dfs(int v,int p=-1){
    sz[v] = 1;
    for(auto to : g[v]){
        if(to.ff==p)continue;
        dfs(to.ff,v);
        sz[v]+=sz[to.ff];
    }
}

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][0][1] = 2*ar; // sobe
    dp[v][1][1] = ar; // fica mas nao escolhi
    dp[v][2][1] = 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][0][i] + dp[to][0][j]);
                // os dois sobem ^ 
                aux[i+j][1] = min(aux[i+j][1],dp[v][1][i] + dp[to][0][j]);
                // nao escolhi ^ 
                aux[i+j][2] = min(aux[i+j][2],dp[v][1][i] + dp[to][2][j]);
                // escolho descer em to ^
                aux[i+j][2] = min(aux[i+j][2],dp[v][2][i] + dp[to][0][j]);
                // ja escolhi e nao é em to ^
            }
        }
     

        for(int i=0;i<=sz[v]+sz[to];i++){

            dp[v][1][i] = min(dp[v][1][i],aux[i][1]);
            dp[v][0][i] = min(dp[v][0][i],aux[i][0]);
            dp[v][2][i] = min(dp[v][2][i],aux[i][2]);
        }

        sz[v]+=sz[to];


    }


}

int32_t main(){
   
    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));
    }
    
    dfs(x);
    
    for(int i=1;i<=n;i++){
        for(int j=0;j<3;j++){
            dp[i][j].resize(sz[i]+ 10);
            rep(KKK,0,sz[i] + 10)dp[i][j][KKK] = 1e9 + 10;
        }
    }
    for(int i=1;i<=n;i++)sz[i] = 0;
    solve(x);

    cout<<min({dp[x][0][k],dp[x][1][k],dp[x][2][k]})<<endl;

}

Subtask #1
20.0 / 20.0

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

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 188 ms 6392 KB Output is correct
2 Correct 187 ms 6788 KB Output is correct
3 Correct 463 ms 205720 KB Output is correct
4 Correct 268 ms 67636 KB Output is correct
5 Correct 203 ms 19448 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 188 ms 6392 KB Output is correct
2 Correct 187 ms 6788 KB Output is correct
3 Correct 463 ms 205720 KB Output is correct
4 Correct 268 ms 67636 KB Output is correct
5 Correct 203 ms 19448 KB Output is correct
6 Correct 188 ms 5240 KB Output is correct
7 Correct 356 ms 121540 KB Output is correct
8 Correct 637 ms 4096 KB Output is correct
9 Correct 477 ms 4464 KB Output is correct
10 Correct 228 ms 5240 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1280 KB Output is correct
2 Correct 5 ms 1280 KB Output is correct
3 Correct 5 ms 1280 KB Output is correct
4 Correct 5 ms 1280 KB Output is correct
5 Correct 5 ms 1280 KB Output is correct
6 Correct 188 ms 6392 KB Output is correct
7 Correct 187 ms 6788 KB Output is correct
8 Correct 463 ms 205720 KB Output is correct
9 Correct 268 ms 67636 KB Output is correct
10 Correct 203 ms 19448 KB Output is correct
11 Correct 188 ms 5240 KB Output is correct
12 Correct 356 ms 121540 KB Output is correct
13 Correct 637 ms 4096 KB Output is correct
14 Correct 477 ms 4464 KB Output is correct
15 Correct 228 ms 5240 KB Output is correct
16 Correct 198 ms 7288 KB Output is correct
17 Correct 191 ms 6904 KB Output is correct
18 Correct 302 ms 82680 KB Output is correct
19 Correct 505 ms 4216 KB Output is correct
20 Correct 230 ms 5376 KB Output is correct
21 Correct 338 ms 116800 KB Output is correct
22 Correct 185 ms 6648 KB Output is correct
23 Correct 509 ms 4216 KB Output is correct
24 Correct 196 ms 5240 KB Output is correct
25 Correct 459 ms 211320 KB Output is correct