Submission #446046

#	Time	Username	Problem	Language	Result	Execution time	Memory
446046		grt	Džumbus (COCI19_dzumbus)	C++17	50 / 110	68 ms	7064 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];
vector<ll> dp[nax];
vector<ll> withme[nax];
int cost[nax];
ll DP[2][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();
		vector<ll> dp2(me + he - 1);
		vector<ll> 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);
	}
}

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);
	}
	for(int i = 1; i <= n; ++i) {
		DP[0][i] = INF;
		DP[1][i] = INF;
	}
	DP[0][0] = 0;
	bool turn = 1;
	int pre = 0;
	for(int i = 1; i <= n; ++i) {
		if(!visited[i]) {
			dfs(i);
			for(int ii = 0; ii < (int)dp[i].size(); ++ii) {
				dp[i][ii] = min(dp[i][ii], withme[i][ii]);
			}
			for(int ii = (int)dp[i].size() - 2; ii >= 0; --ii) {
				dp[i][ii] = min(dp[i][ii], dp[i][ii + 1]);
			}
			int me = (int)dp[i].size();
			for(int cnt1 = 0; cnt1 <= pre; ++cnt1) {
				for(int cnt2 = 0; cnt2 < me; ++cnt2) {
					DP[turn][cnt1 + cnt2] = min(DP[turn ^ 1][cnt1 + cnt2], DP[turn ^ 1][cnt1] + dp[i][cnt2]);
				}
			}
			pre += me - 1;
			turn ^= 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[turn ^ 1][mid] <= x) {
				l = mid + 1;
			} else {
				r = mid - 1;
			}
		}
		cout << l - 1 << "\n";
	}	
}

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