oj.uz

Submission #446043

# Submission time Handle Problem Language Result Execution time Memory
446043 2021-07-20T14:38:15 Z grt Džumbus (COCI19_dzumbus) C++17
20 / 110
 58 ms 5536 KB 
#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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 2700 KB Output is correct
2 Correct 9 ms 3148 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 2700 KB Output is correct
2 Correct 9 ms 3148 KB Output is correct
3 Correct 54 ms 5536 KB Output is correct
4 Correct 54 ms 5448 KB Output is correct
5 Incorrect 58 ms 5444 KB Output isn't correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 2448 KB Output is correct
2 Incorrect 40 ms 2372 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 2700 KB Output is correct
2 Correct 9 ms 3148 KB Output is correct
3 Correct 54 ms 5536 KB Output is correct
4 Correct 54 ms 5448 KB Output is correct
5 Incorrect 58 ms 5444 KB Output isn't correct