제출 #446043

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
446043		grt	Džumbus (COCI19_dzumbus)	C++17	20 / 110	58 ms	5536 KiB

dzumbus

#include <bits/stdc++.h>
#define ST first
#define ND second
#define PB push_back

using namespace std;
using ll = long long;
using pi = pair<int,int>;
using vi = vector<int>;

const int nax = 1000 + 10, INF = 1e9 + 10;
int n, m;
vi V[nax];
bool visited[nax];
vi dp[nax];
vi withme[nax];
int cost[nax];

void dfs(int x) {
	visited[x] = true;
	dp[x].PB(0);
	withme[x].PB(INF);
	dp[x].PB(INF);
	withme[x].PB(INF);
	for(int nbh : V[x]) if(!visited[nbh]) {
		dfs(nbh);
		int me = (int)dp[x].size(), he = (int)dp[nbh].size();
		vi dp2(me + he - 1);
		vi withme2(me + he - 1);
		for(int i = 0; i < me + he - 1; ++i) {
			if(i < me) {
				dp2[i] = dp[x][i];
				withme2[i] = withme[x][i];
			} else {
				dp2[i] = INF;
				withme2[i] = INF;
			}
		}
		for(int cnt1 = 0; cnt1 < me; ++cnt1) {
			for(int cnt2 = 0; cnt2 < he; ++cnt2) {
				withme2[cnt1 + cnt2] = min(withme2[cnt1 + cnt2], withme[x][cnt1] + min(withme[nbh][cnt2], dp[nbh][cnt2]));
				if(cnt2 > 0 && cnt1 > 0) withme2[cnt1 + cnt2] = min(withme2[cnt1 + cnt2], dp[x][cnt1 - 1] + dp[nbh][cnt2 - 1] + cost[nbh] + cost[x]);
				if(cnt1 > 0) withme2[cnt1 + cnt2] = min(withme2[cnt1 + cnt2], dp[x][cnt1 - 1] + withme[nbh][cnt2] + cost[x]);
				if(cnt2 > 0) withme2[cnt1 + cnt2] = min(withme2[cnt1 + cnt2], withme[x][cnt1] + dp[nbh][cnt2 - 1] + cost[nbh]);
			}
		}
		for(int cnt1 = 0; cnt1 < me; ++cnt1) {
			for(int cnt2 = 0; cnt2 < he; ++cnt2) {
				dp2[cnt1 + cnt2] = min(dp2[cnt1 + cnt2], dp[x][cnt1] + min(withme[nbh][cnt2], dp[nbh][cnt2]));
			}
		}
		withme[nbh].clear();
		dp[nbh].clear();
		dp[x].swap(dp2);
		withme[x].swap(withme2);
	}
	//cout << x << ": ";
	//for(int y : dp[x]) cout << y << " ";
	//cout << "\n";
	//cout << x << ": ";
	//for(int y : withme[x]) cout << y << " ";
	//cout << "\n";
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m;
	for(int i = 1; i <= n; ++i) {
		cin >> cost[i];
	}
	for(int a, b, i = 1; i <= m; ++i) {
		cin >> a >> b;
		V[a].PB(b);
		V[b].PB(a);
	}
	dfs(1);
	for(int i = 0; i < (int)dp[1].size(); ++i) {
		dp[1][i] = min(dp[1][i], withme[1][i]);
	}
	for(int i = (int)dp[1].size() - 2; i >= 0; --i) {
		dp[1][i] = min(dp[1][i], dp[1][i + 1]);
	}
	int q;
	cin >> q;
	while(q--) {
		int x;
		cin >> x;
		int l = 0, r = n, mid;
		while(l <= r) {
			mid = (l + r)/2;
			if(dp[1][mid] <= x) {
				l = mid + 1;
			} else {
				r = mid - 1;
			}
		}
		cout << l - 1 << "\n";
	}	
}

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