oj.uz

Submission #420022

# Submission time Handle Problem Language Result Execution time Memory
420022 2021-06-07T23:51:49 Z KhaledFarhat Džumbus (COCI19_dzumbus) C++14
110 / 110
 60 ms 14636 KB 
#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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 8396 KB Output is correct
2 Correct 17 ms 11768 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 8396 KB Output is correct
2 Correct 17 ms 11768 KB Output is correct
3 Correct 56 ms 14636 KB Output is correct
4 Correct 60 ms 12052 KB Output is correct
5 Correct 56 ms 10692 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 2504 KB Output is correct
2 Correct 40 ms 2156 KB Output is correct
3 Correct 58 ms 2756 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 8396 KB Output is correct
2 Correct 17 ms 11768 KB Output is correct
3 Correct 56 ms 14636 KB Output is correct
4 Correct 60 ms 12052 KB Output is correct
5 Correct 56 ms 10692 KB Output is correct
6 Correct 40 ms 2504 KB Output is correct
7 Correct 40 ms 2156 KB Output is correct
8 Correct 58 ms 2756 KB Output is correct
9 Correct 46 ms 3112 KB Output is correct
10 Correct 51 ms 3396 KB Output is correct
11 Correct 51 ms 3052 KB Output is correct