oj.uz

Submission #499886

# Submission time Handle Problem Language Result Execution time Memory
499886 2021-12-29T22:02:38 Z Eyed Džumbus (COCI19_dzumbus) C++14
110 / 110
 308 ms 20556 KB 
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <cmath>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pii;
const ll INF = 1e14;
const ll MOD = 1e9 + 7;
//Problem: https://oj.uz/problem/view/COCI19_dzumbus

ll n, m, q;
ll arr[1001];
vector<ll> forest[1001];

vector<ll> dpArr[1001][3];

bool vis[1001];
void dfs2(ll x) {
	vis[x] = true;
	for (ll node : forest[x]) if (!vis[node]) dfs2(node);
}

void dfs(ll x, ll p) {
	dpArr[x][0].resize(1);
	dpArr[x][1].resize(1);
	dpArr[x][2].resize(1);
	dpArr[x][0][0] = 0; //disregarded
	dpArr[x][1][0] = arr[x]; //not connected yet, but exist at top
	dpArr[x][2][0] = INF; //already connected
	for (ll node : forest[x]) {
		if (node == p) continue;
		dfs(node, x);
		ll t = node;
		ll s = dpArr[node][0].size() + dpArr[x][0].size() + 1;
		vector<ll> nArr0(s, INF);
		vector<ll> nArr1(s, INF);
		vector<ll> nArr2(s, INF);
		for (ll i = 0; i < dpArr[x][0].size(); ++i) {
			for (ll j = 0; j < dpArr[node][0].size(); ++j) {
				nArr0[i + j] = min(nArr0[i+j], dpArr[x][0][i] + min(dpArr[t][0][j], min(dpArr[t][1][j], dpArr[t][2][j])));
				nArr1[i + j] = min(nArr1[i + j], dpArr[x][1][i] + dpArr[t][0][j]);
				nArr2[i + j] = min(nArr2[i + j], dpArr[x][2][i] + min(dpArr[t][2][j], dpArr[t][0][j]));
				nArr2[i + j + 1] = min(nArr2[i + j + 1], dpArr[x][2][i] + dpArr[t][1][j]);
				nArr2[i + j + 2] = min(nArr2[i + j + 2], dpArr[x][1][i] + dpArr[t][1][j]);
				nArr2[i + j + 1] = min(nArr2[i + j + 1], dpArr[x][1][i] + dpArr[t][2][j]);
			}
		}
		//for (ll j = 0; j < s; ++j) nArr1[j] = min(nArr1[j], nArr0[j]);
		dpArr[x][0] = nArr0;
		dpArr[x][1] = nArr1;
		dpArr[x][2] = nArr2;
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> m;
	for (ll i = 1; i <= n; ++i) cin >> arr[i];
	arr[0] = 1e9 + 1;
	for (ll i = 0; i < m; ++i) {
		ll a, b;
		cin >> a >> b;
		forest[a].push_back(b);
		forest[b].push_back(a);
	}
	for (ll i = 1; i <= n; ++i) {
		if (!vis[i]) {
			dfs2(i);
			forest[0].push_back(i);
			forest[i].push_back(0);
		}
	}
	dfs(0, 0);
	//for (ll i = 0; i < dpArr[0][0].size(); ++i) {
	//	dpArr[0][0][i] = min(dpArr[0][0][i], min(dpArr[0][1][i], dpArr[0][2][i]));
	//	if (i == 2) dpArr[0][0][1] = dpArr[0][0][2];
	//	//cout << dpArr[0][0][i] << " ";
	//}
	
	dpArr[0][0][1] = dpArr[0][0][2];

	//cout << endl;
	cin >> q;
	for (ll i = 0; i < q; ++i) {
		ll s;
		cin >> s;
		ll l = 0;
		ll r = (dpArr[0][0].size() - 1)/2;
		while (l < r) {
			ll mid = (l + r + 1) / 2;
			if (dpArr[0][0][2*mid] <= s) l = mid;
			else r = mid - 1;
		}
		ll ans = 2*l;
		l = 0;
		r = (dpArr[0][0].size()) / 2 - 1;
		while (l < r) {
			ll mid = (l + r + 1) / 2;
			if (dpArr[0][0][2 * mid + 1] <= s) l = mid;
			else r = mid - 1;
		}
		ans = max((dpArr[0][0][1] <= s ? 2*l+1 : 0), ans);
		cout << ans << endl;
	}
	

	return 0;
}

Compilation message

dzumbus.cpp: In function 'void dfs(ll, ll)':
dzumbus.cpp:44:20: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |   for (ll i = 0; i < dpArr[x][0].size(); ++i) {
      |                  ~~^~~~~~~~~~~~~~~~~~~~
dzumbus.cpp:45:21: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |    for (ll j = 0; j < dpArr[node][0].size(); ++j) {
      |                   ~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 14540 KB Output is correct
2 Correct 20 ms 20556 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 14540 KB Output is correct
2 Correct 20 ms 20556 KB Output is correct
3 Correct 293 ms 19856 KB Output is correct
4 Correct 308 ms 19020 KB Output is correct
5 Correct 281 ms 17020 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 293 ms 1388 KB Output is correct
2 Correct 266 ms 1152 KB Output is correct
3 Correct 271 ms 2696 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 14540 KB Output is correct
2 Correct 20 ms 20556 KB Output is correct
3 Correct 293 ms 19856 KB Output is correct
4 Correct 308 ms 19020 KB Output is correct
5 Correct 281 ms 17020 KB Output is correct
6 Correct 293 ms 1388 KB Output is correct
7 Correct 266 ms 1152 KB Output is correct
8 Correct 271 ms 2696 KB Output is correct
9 Correct 274 ms 3688 KB Output is correct
10 Correct 291 ms 3704 KB Output is correct
11 Correct 294 ms 3392 KB Output is correct