oj.uz

답안 #716942

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
716942 2023-03-31T13:05:08 Z Dan4Life Museum (CEOI17_museum) C++17
80 / 100
 3000 ms 835024 KB 
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) a.begin(),a.end()
const int mxN=(int)1e4+10;
const int LINF = (int)1e9;
int n, k, s, sub[mxN];
vector<pair<int,int>> adj[mxN];
int dp[mxN][mxN][2], dp2[mxN][mxN][2];

int findSize(int s, int p){
	sub[s]=1;
	for(auto [u,w] : adj[s])
		if(u!=p) sub[s]+=findSize(u,s);
	return sub[s];
}

void dfs(int s, int p){
	vector<pair<int,int>> v; v.clear();
	for(auto [u,w] : adj[s])
		if(u!=p) dfs(u,s), v.pb({u,w});
	dp[s][1][0]=dp[s][1][1]=0;
	if(!sz(v)) return;
	for(int i = 0; i <= sz(v); i++)
		for(int j = 0; j <= min(k,sub[s]); j++)
			dp2[i][j][0]=dp2[i][j][1]=LINF;
	dp2[0][0][0] = dp2[0][0][1] = 0; int tot = 0;
	for(int i = 1; i <= sz(v); i++){
		auto u = v[i-1].se;
		for(int j = 0; j <= min(k,sub[s]); j++){
			for(int x = 0; x < 2; x++){
				dp2[i][j][x] = min(dp2[i][j][x],dp2[i-1][j][x]);
				for(int l = 1; l <= j; l++){
					dp2[i][j][x] = min(dp2[i][j][x], dp2[i-1][j-l][x]+
					dp[v[i-1].fi][l][1]+2*u);
					if(x) continue;
					dp2[i][j][x] = min(dp2[i][j][x], dp2[i-1][j-l][1]+
					dp[v[i-1].fi][l][0]+u);
				}
				
			}
		}
		tot+=sub[u];
	}
	for(int i = 2; i <= min(k,sub[s]); i++)
		for(int j = 0; j < 2; j++)
			dp[s][i][j] = min(dp[s][i][j],dp2[sz(v)][i-1][j]);
}
 
int32_t main()
{
    ios_base::sync_with_stdio(false); cin.tie(0);
    cin >> n >> k >> s;
	for(int i = 0; i < mxN; i++)
		for(int j = 0; j < mxN; j++)
			dp[i][j][0]=dp[i][j][1]=LINF;
	for(int i = 1; i < n; i++){
		int a, b, c; cin >> a >> b >> c;
		adj[a].pb({b,c}), adj[b].pb({a,c});
	}
	findSize(s,-1); dfs(s,-1); cout << dp[s][k][0];
}

Subtask #1
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 336 ms 784816 KB Output is correct
2 Correct 329 ms 784852 KB Output is correct
3 Correct 337 ms 784832 KB Output is correct
4 Correct 336 ms 784864 KB Output is correct
5 Correct 334 ms 784928 KB Output is correct

Subtask #2
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 369 ms 785392 KB Output is correct
2 Correct 395 ms 785492 KB Output is correct
3 Correct 566 ms 786064 KB Output is correct
4 Correct 501 ms 785648 KB Output is correct
5 Correct 450 ms 785452 KB Output is correct

Subtask #3
35.0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 369 ms 785392 KB Output is correct
2 Correct 395 ms 785492 KB Output is correct
3 Correct 566 ms 786064 KB Output is correct
4 Correct 501 ms 785648 KB Output is correct
5 Correct 450 ms 785452 KB Output is correct
6 Correct 389 ms 785468 KB Output is correct
7 Correct 660 ms 786004 KB Output is correct
8 Correct 851 ms 835024 KB Output is correct
9 Correct 844 ms 795628 KB Output is correct
10 Correct 801 ms 786124 KB Output is correct

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 336 ms 784816 KB Output is correct
2 Correct 329 ms 784852 KB Output is correct
3 Correct 337 ms 784832 KB Output is correct
4 Correct 336 ms 784864 KB Output is correct
5 Correct 334 ms 784928 KB Output is correct
6 Correct 369 ms 785392 KB Output is correct
7 Correct 395 ms 785492 KB Output is correct
8 Correct 566 ms 786064 KB Output is correct
9 Correct 501 ms 785648 KB Output is correct
10 Correct 450 ms 785452 KB Output is correct
11 Correct 389 ms 785468 KB Output is correct
12 Correct 660 ms 786004 KB Output is correct
13 Correct 851 ms 835024 KB Output is correct
14 Correct 844 ms 795628 KB Output is correct
15 Correct 801 ms 786124 KB Output is correct
16 Correct 872 ms 785512 KB Output is correct
17 Execution timed out 3043 ms 785608 KB Time limit exceeded
18 Halted 0 ms 0 KB -