oj.uz

Submission #712525

# Submission time Handle Problem Language Result Execution time Memory
712525 2023-03-19T03:48:16 Z yuseok0803 Museum (CEOI17_museum) C++14
100 / 100
 473 ms 746232 KB 
#include <stdio.h>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <algorithm>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <stack>
#include <ctype.h>
#define p(x,y) pair<x, y>
#define pii pair<int, int>
#define v(x) vector<x>
#define q(x) queue<x>
#define pq(x) priority_queue<x>
#define uppq(x, comp) priority_queue<x, vector<x>, comp>
#define st(x) set<x>  
#define m(x, y) map<x, y>
#define fi(s,e) for(int i=s;i<e;i++)
#define fj(s,e) for(int j=s;j<e;j++)
#define fk(s,e) for(int k=s;k<e;k++)
typedef long long int ll;
typedef unsigned long long int ull;
typedef __int128 ulll;
using namespace std;

int n,need,x;
v(pii) pushvec;
v(v(pii)) vec;
int cnt[100010];
int dp[10010][10010][2];
//dp[start][visited rooms cnt][start==end?]

void find(int now, int parent){
	dp[now][1][0]=0;
	dp[now][1][1]=0;
	fi(2, need+1) dp[now][i][0] = dp[now][i][1] = 999999999;
	
	cnt[now]=1;
	int sz = vec[now].size();
	fi(0,sz){
		pii next = vec[now][i];
		if(next.first == parent) continue;
		
		find(next.first, now);
		
		for(int j = cnt[now]; j >= 1; j--){
			fk(1, cnt[next.first]+1){
				if(j + k > need) break;
				
				dp[now][j+k][1] = min(dp[now][j+k][1], dp[now][j][1]+dp[next.first][k][1]+next.second*2);
				dp[now][j+k][0] = min({dp[now][j+k][0], dp[next.first][k][1]+dp[now][j][0]+next.second*2, dp[now][j][1]+next.second+dp[next.first][k][0]});
				
			}
		}
		
		cnt[now] += cnt[next.first];
	}
	
	return;
}

int main(void){
	scanf("%d%d%d",&n,&need,&x);
	fi(0,n+1) vec.push_back(pushvec);
	
	fi(1,n){
		int a,b,c;
		scanf("%d%d%d",&a,&b,&c);
		vec[a].push_back({b,c});
		vec[b].push_back({a,c});
	}
	
	find(x, x);
	
	printf("%d\n", dp[x][need][0]);
	return 0;
}

Compilation message

museum.cpp: In function 'int main()':
museum.cpp:65:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   65 |  scanf("%d%d%d",&n,&need,&x);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
museum.cpp:70:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   70 |   scanf("%d%d%d",&a,&b,&c);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 50368 KB Output is correct
2 Correct 29 ms 50360 KB Output is correct
3 Correct 34 ms 50732 KB Output is correct
4 Correct 30 ms 50344 KB Output is correct
5 Correct 36 ms 50284 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 50368 KB Output is correct
2 Correct 29 ms 50360 KB Output is correct
3 Correct 34 ms 50732 KB Output is correct
4 Correct 30 ms 50344 KB Output is correct
5 Correct 36 ms 50284 KB Output is correct
6 Correct 28 ms 50372 KB Output is correct
7 Correct 33 ms 50572 KB Output is correct
8 Correct 65 ms 50496 KB Output is correct
9 Correct 52 ms 50400 KB Output is correct
10 Correct 37 ms 50400 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 30 ms 50368 KB Output is correct
7 Correct 29 ms 50360 KB Output is correct
8 Correct 34 ms 50732 KB Output is correct
9 Correct 30 ms 50344 KB Output is correct
10 Correct 36 ms 50284 KB Output is correct
11 Correct 28 ms 50372 KB Output is correct
12 Correct 33 ms 50572 KB Output is correct
13 Correct 65 ms 50496 KB Output is correct
14 Correct 52 ms 50400 KB Output is correct
15 Correct 37 ms 50400 KB Output is correct
16 Correct 83 ms 120648 KB Output is correct
17 Correct 280 ms 433212 KB Output is correct
18 Correct 84 ms 120904 KB Output is correct
19 Correct 111 ms 120752 KB Output is correct
20 Correct 80 ms 120896 KB Output is correct
21 Correct 450 ms 745920 KB Output is correct
22 Correct 445 ms 745672 KB Output is correct
23 Correct 473 ms 745712 KB Output is correct
24 Correct 439 ms 745696 KB Output is correct
25 Correct 445 ms 746232 KB Output is correct