oj.uz

답안 #780404

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
780404 2023-07-12T08:49:30 Z quochuy147 Museum (CEOI17_museum) C++14
100 / 100
 674 ms 784448 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+2;
const int LINF = (int)1e9;
int n, k, s, sub[mxN];
vector<pair<int,int>> adj[mxN];
int dp[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){
	for(int tot = 1; auto [u,w] : adj[s]){ 
		if(u==p) continue; 
		dfs(u,s); tot+=sub[u];
		for(int i = tot; i >= 2; i--)
            for(int j = max(0, i-tot+sub[u]); j<=min(i,sub[u]); j++)
				dp[s][i][0] = min(dp[s][i][0], dp[s][i-j][0] + dp[u][j][1]+2*w),
				dp[s][i][0] = min(dp[s][i][0], dp[s][i-j][1]+dp[u][j][0]+w),
				dp[s][i][1] = min(dp[s][i][1], dp[s][i-j][1]+dp[u][j][1]+2*w);
	}
}
 
int32_t main()
{
    ios_base::sync_with_stdio(false); cin.tie(0);
    cin >> n >> k >> s;
	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});
	}
	for(int i=1; i<=n; i++){
        for(int j=2; j<=n; j++){
            dp[i][j][0] = dp[i][j][1] = LINF;
        }
    }
	findSize(s,-1); dfs(s,-1); cout << dp[s][k][0];
}

Compilation message

museum.cpp: In function 'int findSize(int, int)':
museum.cpp:16:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   16 |  for(auto [u,w] : adj[s])
      |           ^
museum.cpp: In function 'void dfs(int, int)':
museum.cpp:22:19: warning: range-based 'for' loops with initializer only available with '-std=c++2a' or '-std=gnu++2a'
   22 |  for(int tot = 1; auto [u,w] : adj[s]){
      |                   ^~~~
museum.cpp:22:24: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   22 |  for(int tot = 1; auto [u,w] : adj[s]){
      |                        ^

Subtask #1
20.0 / 20.0

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

Subtask #2
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 439 ms 783924 KB Output is correct
2 Correct 392 ms 783964 KB Output is correct
3 Correct 503 ms 784448 KB Output is correct
4 Correct 434 ms 784104 KB Output is correct
5 Correct 418 ms 784064 KB Output is correct

Subtask #3
35.0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 439 ms 783924 KB Output is correct
2 Correct 392 ms 783964 KB Output is correct
3 Correct 503 ms 784448 KB Output is correct
4 Correct 434 ms 784104 KB Output is correct
5 Correct 418 ms 784064 KB Output is correct
6 Correct 454 ms 784040 KB Output is correct
7 Correct 463 ms 784284 KB Output is correct
8 Correct 674 ms 784036 KB Output is correct
9 Correct 533 ms 784236 KB Output is correct
10 Correct 418 ms 784088 KB Output is correct

Subtask #4
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 1 ms 568 KB Output is correct
6 Correct 439 ms 783924 KB Output is correct
7 Correct 392 ms 783964 KB Output is correct
8 Correct 503 ms 784448 KB Output is correct
9 Correct 434 ms 784104 KB Output is correct
10 Correct 418 ms 784064 KB Output is correct
11 Correct 454 ms 784040 KB Output is correct
12 Correct 463 ms 784284 KB Output is correct
13 Correct 674 ms 784036 KB Output is correct
14 Correct 533 ms 784236 KB Output is correct
15 Correct 418 ms 784088 KB Output is correct
16 Correct 420 ms 784000 KB Output is correct
17 Correct 422 ms 784076 KB Output is correct
18 Correct 437 ms 784220 KB Output is correct
19 Correct 560 ms 784064 KB Output is correct
20 Correct 441 ms 784112 KB Output is correct
21 Correct 465 ms 784184 KB Output is correct
22 Correct 401 ms 784068 KB Output is correct
23 Correct 568 ms 784072 KB Output is correct
24 Correct 403 ms 784124 KB Output is correct
25 Correct 517 ms 784432 KB Output is correct