oj.uz

답안 #244490

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
244490 2020-07-04T07:20:21 Z kshitij_sodani Museum (CEOI17_museum) C++17
80 / 100
 333 ms 176504 KB 
#include <bits/stdc++.h>
using namespace std;
typedef int64_t llo;
#define mp make_pair
#define pb push_back
#define a first 
#define b second
//#define endl '\n'

int n,k,x;
vector<pair<int,int>> adj[10001];
int dp[10001][10001][2];
//0-return
//1-don't return
int ss[1001];
int min2(int aa,int bb){
	if(aa==0){
		return bb;
	}
	return min(aa,bb);
}
void dfs(int no,int par=-1){

	ss[no]=1;

	for(auto j:adj[no]){
		if(j.a==par){
			continue;
		}
		dfs(j.a,no);
		ss[no]+=ss[j.a];
	}
	int cur=0;
	dp[no][1][1]=0;
	dp[no][1][0]=0;
	for(auto j:adj[no]){
		if(j.a==par){
			continue;
		}
		cur+=ss[j.a];
		for(int i=cur+1;i>=2;i--){
			for(int kk=max(1,i-(cur-ss[j.a]+1));kk<=min(i-1,ss[j.a]);kk++){
				if(i-kk>cur-ss[j.a]+1){
					continue;
				}
				else{
					/*if(dp[no][i-kk][0]==-1){
						cout<<no<<","<<i-kk<<','<<0<<endl;
					}*/
				}
				//if(dp[no][i-kk][0]>-1){
					dp[no][i][0]=min2(dp[no][i][0],dp[no][i-kk][0]+dp[j.a][kk][0]+2*j.b);
					dp[no][i][1]=min2(dp[no][i][1],dp[no][i-kk][0]+dp[j.a][kk][1]+j.b);
				//}
				//if(dp[no][i-kk][1]>-1){
					dp[no][i][1]=min2(dp[no][i][1],dp[no][i-kk][1]+dp[j.a][kk][0]+2*j.b);
				//}
			}
		}
	}
	/*cout<<no<<endl;
	for(int j=1;j<=ss[no];j++){
		cout<<dp[no][j][0]<<",";
	}
	cout<<endl;
	for(int j=1;j<=ss[no];j++){
		cout<<dp[no][j][1]<<",";
	}
	cout<<endl;
*/


}



int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin>>n>>k>>x;
	x--;
	for(int i=0;i<n-1;i++){
		int aa,bb,cc;
		cin>>aa>>bb>>cc;
		aa--;
		bb--;
		adj[aa].pb({bb,cc});
		adj[bb].pb({aa,cc});
	}
	/*for(int i=0;i<n;i++){
		for(int j=1;j<=k;j++){
			dp[i][j][0]=-1;
			dp[i][j][1]=-1;
		}
	}*/
	dfs(x);
	cout<<min(dp[x][k][1],dp[x][k][0])<<endl;
	



	return 0;
}

Subtask #1
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 640 KB Output is correct
2 Correct 5 ms 640 KB Output is correct
3 Correct 5 ms 640 KB Output is correct
4 Correct 5 ms 640 KB Output is correct
5 Correct 5 ms 640 KB Output is correct

Subtask #2
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 221 ms 44152 KB Output is correct
2 Correct 227 ms 44540 KB Output is correct
3 Correct 333 ms 176504 KB Output is correct
4 Correct 252 ms 84984 KB Output is correct
5 Correct 230 ms 52984 KB Output is correct

Subtask #3
35.0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 221 ms 44152 KB Output is correct
2 Correct 227 ms 44540 KB Output is correct
3 Correct 333 ms 176504 KB Output is correct
4 Correct 252 ms 84984 KB Output is correct
5 Correct 230 ms 52984 KB Output is correct
6 Correct 224 ms 43660 KB Output is correct
7 Correct 298 ms 120824 KB Output is correct
8 Correct 302 ms 42744 KB Output is correct
9 Correct 262 ms 42872 KB Output is correct
10 Correct 215 ms 43384 KB Output is correct

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 640 KB Output is correct
2 Correct 5 ms 640 KB Output is correct
3 Correct 5 ms 640 KB Output is correct
4 Correct 5 ms 640 KB Output is correct
5 Correct 5 ms 640 KB Output is correct
6 Correct 221 ms 44152 KB Output is correct
7 Correct 227 ms 44540 KB Output is correct
8 Correct 333 ms 176504 KB Output is correct
9 Correct 252 ms 84984 KB Output is correct
10 Correct 230 ms 52984 KB Output is correct
11 Correct 224 ms 43660 KB Output is correct
12 Correct 298 ms 120824 KB Output is correct
13 Correct 302 ms 42744 KB Output is correct
14 Correct 262 ms 42872 KB Output is correct
15 Correct 215 ms 43384 KB Output is correct
16 Correct 224 ms 44792 KB Output is correct
17 Correct 226 ms 44500 KB Output is correct
18 Correct 272 ms 94712 KB Output is correct
19 Correct 273 ms 42744 KB Output is correct
20 Correct 230 ms 43512 KB Output is correct
21 Incorrect 291 ms 117752 KB Output isn't correct
22 Halted 0 ms 0 KB -