제출 #420022

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
420022		KhaledFarhat	Džumbus (COCI19_dzumbus)	C++14	110 / 110	60 ms	14636 KiB

dzumbus

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

typedef long long 		ll;

const ll LLONG_INF = LLONG_MAX / 2;
const int INT_INF = INT_MAX / 2;
const int MAX = 1009;
int n, d[MAX];
bool isVisited[MAX];
vector<int> adj[MAX];
vector<vector<ll>> dp[MAX];

template<typename T>
void Minimize(T& a, T b) {
	a = min(a, b);
}

vector<ll> MergeDp(const vector<ll>& a, const vector<ll>& b) {
	vector<ll> c(a.size() + b.size() - 1, LLONG_INF);
	
	for (int i = 0; i < (int)a.size(); ++i) {
		for (int j = 0; j < (int)b.size(); ++j) {
			Minimize(c[i + j], a[i] + b[j]);
		}
	}
	
	return c;
}

vector<ll> GetMin(vector<ll> a, const vector<ll>& b) {
	while (a.size() < b.size()) {
		a.push_back(LLONG_INF);
	}
	
	for (int i = 0; i < (int)a.size(); ++i) {
		Minimize(a[i], b[i]);
	}
	
	return a;
}

void MergeSubtree(int node, int child) {
	dp[node][0] = MergeDp(dp[node][0], GetMin(dp[child][0], dp[child][2]));
	dp[node][2] = GetMin(MergeDp(dp[node][2], GetMin(dp[child][0], GetMin(dp[child][1], dp[child][2]))),
						 MergeDp(dp[node][1], GetMin(dp[child][1], dp[child][2])));
	dp[node][1] = MergeDp(dp[node][1], dp[child][0]);
}

// dp[node][0] -> node was not selected
// dp[node][1] -> node was selected but no child was selected
// dp[node][2] -> node was selected and at least one child was selected
void Dfs(int node, int parent) {
	isVisited[node] = true;
		
	dp[node].resize(3);
	
	dp[node][0] = {0, LLONG_INF};
	dp[node][1] = {LLONG_INF, d[node]};
	dp[node][2] = {LLONG_INF, LLONG_INF};
		
	for (int child : adj[node]) {
		if (child != parent) {
			if (isVisited[child] == false) {
				Dfs(child, node);
			}
			
			MergeSubtree(node, child);
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	int n, m;
	cin >> n >> m;
	
	d[0] = INT_INF;
	
	for (int i = 1; i <= n; ++i) {
		cin >> d[i];
	}
	
	for (int i = 1; i <= m; ++i) {
		int a, b;
		cin >> a >> b;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
	
	for (int i = 1; i <= n; ++i) {
		if (isVisited[i] == false) {
			Dfs(i, -1);
			adj[0].push_back(i);
		}
	}
	
	Dfs(0, -1);
	
	for (int i = n - 1; i >= 0; --i) {
		Minimize(dp[0][0][i], dp[0][0][i + 1]);
	}
	
	int q;
	cin >> q;
	
	while (q--) {
		int s;
		cin >> s;
		
		cout << upper_bound(dp[0][0].begin(), dp[0][0].end(), (ll)s) - dp[0][0].begin() - 1 << "\n";
	}
	
	return 0;
}

• Subtask 1: 20 / 20
• Subtask 2: 30 / 30
• Subtask 3: 30 / 30
• Subtask 4: 30 / 30