| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 223954 |
2020-04-16T22:28:03 Z |
NaimSS |
Museum (CEOI17_museum) |
C++14 |
|
157 ms |
13176 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 ^
}
}
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;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
12416 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
157 ms |
13176 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
157 ms |
13176 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
12416 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
