Submission #885927

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
885927	2023-12-11T06:57:23 Z	serifefedartar	Džumbus (COCI19_dzumbus)	C++17	Compilation error	0 ms	0 KB

dzumbus

#include <bits/stdc++.h>
using namespace std;
 
#define fast ios::sync_with_stdio(0);cin.tie(0);
#define s second
#define f first
typedef long long ll;
const ll MOD = 30013;
const ll LOGN = 21;
const ll MAXN = 1100;
#define int long long

vector<vector<int>> graph;
vector<int> D, dp[MAXN][3]; 

vector<int> add(vector<int> &A, vector<int> &B) {
	vector<int> res(A.size() + B.size() - 1, 1e12);
	for (int i = 0; i < A.size(); i++) {
		for (int j = 0; j < B.size(); j++)
			res[i+j] = min(res[i+j], A[i] + B[j]);
	}
	return res;
}

vector<int> minimize(vector<int> A, vector<int> &B) {
	while (A.size() < B.size())
		A.push_back(1e12);
	for (int i = 0; i < B.size(); i++)
		A[i] = min(A[i], B[i]);
	return A;
}

int vis[MAXN];
void dfs(int node, int parent) {
	vis[node] = 1;
	dp[node][0] = {0};
	dp[node][1] = {(ll)1e12, D[node]};
	for (auto u : graph[node]) {
		if (u == parent)
			continue;
		dfs(u, node);
		dp[node][0] = add(dp[node][0], minimize(dp[u][0], dp[u][2]));
		dp[node][1] = add(dp[node][1], dp[u][0]);
		dp[node][2] = minimize(add(dp[node][1], minimize(dp[u][1], dp[u][2])),
							add(dp[node][2], minimize(dp[u][1], minimize(dp[u][2], dp[u][0]))));
	}
}

signed main() {
	fast
	int N, M, a, b;
	cin >> N >> M;

	graph = vector<vector<int>>(N+1, vector<int>());
	D = vector<int>(N+1);
	for (int i = 1; i <= N; i++)
		cin >> D[i];
	for (int i = 0; i < M; i++) {
		cin >> a >> b;
		graph[a].push_back(b);
		graph[b].push_back(a);
	}

	vector<int> res = {0};
	for (int i = 1; i <= N; i++) {
		if (!vis[i]) {
			dfs(i, i);
			res = add(res, minimize(dp[i][0], dp[i][2]));
		}
	}


	for (int i = (int)res.size() - 2; i >= 0; i--)
		res[i] = min(res[i+1], res[i]);

	int Q;
	cin >> Q;
	while (Q--) {
		int val;
		cin >> val;

		int q = upper_bound(res.begin(), res.end(), val) - res.begin() - 1;
		cout << q << "\n";
	}
}

Compilation message

dzumbus.cpp: In function 'std::vector<long long int> add(std::vector<long long int>&, std::vector<long long int>&)':
dzumbus.cpp:18:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |  for (int i = 0; i < A.size(); i++) {
      |                  ~~^~~~~~~~~~
dzumbus.cpp:19:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |   for (int j = 0; j < B.size(); j++)
      |                   ~~^~~~~~~~~~
dzumbus.cpp: In function 'std::vector<long long int> minimize(std::vector<long long int>, std::vector<long long int>&)':
dzumbus.cpp:28:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |  for (int i = 0; i < B.size(); i++)
      |                  ~~^~~~~~~~~~
dzumbus.cpp: In function 'void dfs(long long int, long long int)':
dzumbus.cpp:42:42: error: cannot bind non-const lvalue reference of type 'std::vector<long long int>&' to an rvalue of type 'std::vector<long long int>'
   42 |   dp[node][0] = add(dp[node][0], minimize(dp[u][0], dp[u][2]));
      |                                  ~~~~~~~~^~~~~~~~~~~~~~~~~~~~
dzumbus.cpp:16:46: note:   initializing argument 2 of 'std::vector<long long int> add(std::vector<long long int>&, std::vector<long long int>&)'
   16 | vector<int> add(vector<int> &A, vector<int> &B) {
      |                                 ~~~~~~~~~~~~~^
dzumbus.cpp:44:51: error: cannot bind non-const lvalue reference of type 'std::vector<long long int>&' to an rvalue of type 'std::vector<long long int>'
   44 |   dp[node][2] = minimize(add(dp[node][1], minimize(dp[u][1], dp[u][2])),
      |                                           ~~~~~~~~^~~~~~~~~~~~~~~~~~~~
dzumbus.cpp:16:46: note:   initializing argument 2 of 'std::vector<long long int> add(std::vector<long long int>&, std::vector<long long int>&)'
   16 | vector<int> add(vector<int> &A, vector<int> &B) {
      |                                 ~~~~~~~~~~~~~^
dzumbus.cpp:45:52: error: cannot bind non-const lvalue reference of type 'std::vector<long long int>&' to an rvalue of type 'std::vector<long long int>'
   45 |        add(dp[node][2], minimize(dp[u][1], minimize(dp[u][2], dp[u][0]))));
      |                                            ~~~~~~~~^~~~~~~~~~~~~~~~~~~~
dzumbus.cpp:25:50: note:   initializing argument 2 of 'std::vector<long long int> minimize(std::vector<long long int>, std::vector<long long int>&)'
   25 | vector<int> minimize(vector<int> A, vector<int> &B) {
      |                                     ~~~~~~~~~~~~~^
dzumbus.cpp: In function 'int main()':
dzumbus.cpp:68:27: error: cannot bind non-const lvalue reference of type 'std::vector<long long int>&' to an rvalue of type 'std::vector<long long int>'
   68 |    res = add(res, minimize(dp[i][0], dp[i][2]));
      |                   ~~~~~~~~^~~~~~~~~~~~~~~~~~~~
dzumbus.cpp:16:46: note:   initializing argument 2 of 'std::vector<long long int> add(std::vector<long long int>&, std::vector<long long int>&)'
   16 | vector<int> add(vector<int> &A, vector<int> &B) {
      |                                 ~~~~~~~~~~~~~^