Submission #349196

#	Time	Username	Problem	Language	Result	Execution time	Memory
349196		arnold518	Museum (CEOI17_museum)	C++14	100 / 100	475 ms	360348 KiB

museum

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 1e4;
const ll INF = 1e18;

int N, K, R;
vector<pii> adj[MAXN+10];

int sz[MAXN+10];
ll dp1[MAXN+10][MAXN+10], dp2[MAXN+10][MAXN+10];
ll T1[MAXN+10], T2[MAXN+10];

void dfs(int now, int bef)
{
	//printf("%d %d\n", now, bef);
	sz[now]=1;

	dp1[now][0]=INF;
	dp1[now][1]=0;
	dp2[now][0]=INF;
	dp2[now][1]=0;

	for(auto nxt : adj[now])
	{
		if(nxt.first==bef) continue;
		dfs(nxt.first, now);

		for(int i=0; i<=sz[now]+sz[nxt.first]; i++) T1[i]=T2[i]=INF;
		for(int i=0; i<=sz[now]; i++)
		{
			for(int j=0; j<=sz[nxt.first]; j++)
			{
				if(j)
				{
					T1[i+j]=min(T1[i+j], dp1[now][i]+dp2[nxt.first][j]+nxt.second*2);
					T1[i+j]=min(T1[i+j], dp2[now][i]+dp1[nxt.first][j]+nxt.second);
					T2[i+j]=min(T2[i+j], dp2[now][i]+dp2[nxt.first][j]+nxt.second*2);
				}
				else
				{
					T1[i+j]=min(T1[i+j], dp1[now][i]);
					T2[i+j]=min(T2[i+j], dp2[now][i]);
				}
			}
		}
		for(int i=0; i<=sz[now]+sz[nxt.first]; i++)
		{
			dp1[now][i]=T1[i];
			dp2[now][i]=T2[i];
		}
		sz[now]+=sz[nxt.first];
	}
}

int main()
{
	scanf("%d%d%d", &N, &K, &R);
	for(int i=1; i<N; i++)
	{
		int u, v, w;
		scanf("%d%d%d", &u, &v, &w);
		adj[u].push_back({v, w});
		adj[v].push_back({u, w});
	}

	dfs(R, R);
	printf("%lld\n", dp1[R][K]);
}

Compilation message (stderr)

museum.cpp: In function 'int main()':
museum.cpp:62:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   62 |  scanf("%d%d%d", &N, &K, &R);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
museum.cpp:66:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   66 |   scanf("%d%d%d", &u, &v, &w);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 20 / 20
• Subtask 2: 25 / 25
• Subtask 3: 35 / 35
• Subtask 4: 20 / 20