Submission #499871

#	Time	Username	Problem	Language	Result	Execution time	Memory
499871		Eyed	Džumbus (COCI19_dzumbus)	C++14	0 / 110	272 ms	20556 KiB

dzumbus

#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] = INF;
	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] << " ";
	}
	//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;
		while (l < r) {
			ll mid = (l + r + 1) / 2;
			if (dpArr[0][0][mid] <= s) l = mid;
			else r = mid - 1;
		}
		cout << l << endl;
	}
	

	return 0;
}

Compilation message (stderr)

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) {
      |                   ~~^~~~~~~~~~~~~~~~~~~~~~~
dzumbus.cpp: In function 'int main()':
dzumbus.cpp:82:19: 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]
   82 |  for (ll i = 0; i < dpArr[0][0].size(); ++i) {
      |                 ~~^~~~~~~~~~~~~~~~~~~~

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