# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
975311 |
2024-05-04T18:23:28 Z |
dosts |
Museum (CEOI17_museum) |
C++17 |
|
1643 ms |
827728 KB |
//Dost SEFEROĞLU
#pragma GCC optimize("O3,unroll-loops,Ofast")
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
#define ff first
#define ss second
#define sp << " " <<
#define vi vector<int>
const int N = 5e3+100,inf = 1e18,MOD = 998244353;
int dp[N][2][N];
vector<pii> edges[N];
vi sz(N);
int szs(int node,int p) {
sz[node] = 1;
for (auto it : edges[node]) if (it.ff != p) sz[node]+=szs(it.ff,node);
return sz[node];
}
int K;
void compute(int node,int p) {
int curmx = 1;
for (auto it : edges[node]) {
if (it.ff == p) continue;
int u = it.ff,w = it.ss;
compute(u,node);
curmx+=sz[u];
for (int i=curmx;i>=2;i--) {
for (int j=max(0ll,-curmx+sz[u]+i);j<=min(i,sz[u]);j++) {
dp[node][0][i] = min(dp[node][0][i],dp[node][0][i-j] + dp[u][1][j]+ 2*w);
dp[node][1][i] = min(dp[node][1][i],dp[node][1][i-j] + dp[u][1][j]+ 2*w);
dp[node][0][i] = min(dp[node][0][i],dp[node][1][i-j] + dp[u][0][j] + w);
}
}
}
}
void solve() {
int n,x;
cin >> n >> K >> x;
for (int i=1;i<=n-1;i++) {
int u,v,w;
cin >> u >> v >> w;
edges[u].push_back({v,w});
edges[v].push_back({u,w});
}
for (int i=1;i<=n;i++) for(int j=0;j<2;j++) for (int k=2;k<=n;k++) dp[i][j][k] = inf;
szs(x,x);
compute(x,x);
cout << dp[x][0][K] << endl;
}
signed main() {
ios_base::sync_with_stdio(0);
#ifdef Dodi
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
int t = 1;
//cin >> t;
while (t --> 0) solve();
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2652 KB |
Output is correct |
2 |
Correct |
1 ms |
2652 KB |
Output is correct |
3 |
Correct |
1 ms |
2652 KB |
Output is correct |
4 |
Correct |
1 ms |
2652 KB |
Output is correct |
5 |
Correct |
1 ms |
2652 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
1643 ms |
827728 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
1643 ms |
827728 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2652 KB |
Output is correct |
2 |
Correct |
1 ms |
2652 KB |
Output is correct |
3 |
Correct |
1 ms |
2652 KB |
Output is correct |
4 |
Correct |
1 ms |
2652 KB |
Output is correct |
5 |
Correct |
1 ms |
2652 KB |
Output is correct |
6 |
Runtime error |
1643 ms |
827728 KB |
Execution killed with signal 11 |
7 |
Halted |
0 ms |
0 KB |
- |