Submission #1111971

#	Time	Username	Problem	Language	Result	Execution time	Memory
1111971		VectorLi	Museum (CEOI17_museum)	C++17	100 / 100	673 ms	407752 KiB

museum

#include <bits/stdc++.h>
#define I64 long long

using namespace std;

const int N = 10000;
const I64 A = numeric_limits<I64>::max();

vector<I64> operator + (vector<I64> a, vector<I64> b) {
	int n = (int) a.size(), m = (int) b.size();
	vector<I64> c(n + m - 1, A);
	
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (a[i] < A && b[j] < A) {
				c[i + j] = min(c[i + j], a[i] + b[j]);
			}
		}
	}
	
	return c;
}

vector<I64> min(vector<I64> a, vector<I64> b) {
	int n = (int) a.size();
	vector<I64> c(n);
	
	for (int i = 0; i < n; i++) {
		c[i] = min(a[i], b[i]);
	}
	
	return c;
}

int n, k, S;
vector<pair<int, int>> e[N];

int p[N];
vector<I64> f[N][2];

void DFS(int u) {
	f[u][0] = {0, 0};
	f[u][1] = {0, 0};
	for (auto [v, x] : e[u]) {
		if (v != p[u]) {
			p[v] = u;
			DFS(v);
			
			vector<I64> g[2];
			g[0] = f[v][0];
			g[1] = f[v][1];
//			for (auto &i : g[0]) {
//				if (i < A) {
//					i = i + x;
//				}
//			}
//			for (auto &i : g[1]) {
//				if (i < A) {
//					i = i + x * 2;
//				}
//			}
			for (int i = 1; i < (int) g[0].size(); i++) {
				g[0][i] = g[0][i] + x;
			}
			for (int i = 1; i < (int) g[1].size(); i++) {
				g[1][i] = g[1][i] + x * 2;
			}
			
			f[u][0] = min(f[u][0] + g[1], f[u][1] + g[0]);
			f[u][1] = f[u][1] + g[1];
		}
	}
}

void solve() {
	cin >> n >> k >> S;
	for (int i = 0; i < n - 1; i++) {
		int u, v;
		int x;
		cin >> u >> v >> x;
		u = u - 1, v = v - 1;
		e[u].push_back({v, x});
		e[v].push_back({u, x});
	}
	
	S = S - 1;
	p[S] = 0 - 1;
	DFS(S);
	
//	for (int i = 0; i < n; i++) {
//		for (auto x : f[i][0]) {
//			cout << x << " ";
//		}
//		cout << "\n";
//		for (auto x : f[i][1]) {
//			cout << x << " ";
//		}
//		cout << "\n\n";
//	}
	
	cout << f[S][0][k] << "\n";
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(nullptr);
	solve();
	return 0;
}

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