Submission #726016

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
726016	2023-04-18T10:13:01 Z	SanguineChameleon	Road Closures (APIO21_roads)	C++17	Compilation error	0 ms	0 KB

roads

#include "roads.h"
#include <bits/stdc++.h>
using namespace std;

#define int long long

const int maxN = 1e5 + 20;
const long long inf = 1e18L + 20;

struct segtree {
	int N, rem, node_id;
	vector<int> val;

	void init(int _node_id, vector<pair<int, int>> &pre_adj) {
		node_id = _node_id;
		N = pre_adj.size();
		rem = N;
		val.resize(N);
		for (int i = 0; i < N; i++) {
			val[i] = pre_adj[i].first;
		}
	}

	void update(int pos) {
		val[pos] = 0;
		rem--;
	}

	long long get(int x) {
		x = max(x, 0);
		if (x == 0) {
			return 0;
		}
		if (x > rem) {
			return inf;
		}
		long long res = 0;
		int cnt = 0;
		for (int i = 0; i < N; i++) {
			if (val[i]) {
				res += val[i];
				cnt++;
				if (cnt == x) {
					break;
				}
			}
		}
		return res;
	}
};

vector<pair<int, int>> adj[maxN];
vector<pair<int, int>> pre_adj[maxN];
segtree tree[maxN];
vector<int> bucket[maxN];
int deg[maxN];
bool is_bad[maxN];
bool flag[maxN];
long long dp[maxN][2];
int K;

void dfs(int u, int par) {
	flag[u] = true;
	dp[u][0] = inf;
	dp[u][1] = inf;
	long long sum = 0;
	vector<long long> cost;
	for (auto e: adj[u]) {
		int v = e.first;
		int w = e.second;
		if (v == par) {
			continue;
		}
		dfs(v, u);
		sum += dp[v][1];
		cost.push_back(dp[v][0] + w - dp[v][1]);
	}
	sort(cost.begin(), cost.end());
	int cnt = deg[u] - (par != -1);
	for (int i = 0; i < 2; i++) {
		dp[u][i] = min(dp[u][i], sum + tree[u].get(cnt + i - K));
	}
	for (auto w: cost) {
		sum += w;
		cnt--;
		for (int i = 0; i < 2; i++) {
			dp[u][i] = min(dp[u][i], sum + tree[u].get(cnt + i - K));
		}
	}
}

vector<long long> minimum_closure_costs(int N, vector<int> U, vector<int> V, vector<int> W) {
	for (int i = 0; i < N - 1; i++) {
		pre_adj[U[i]].push_back({W[i], V[i]});
		pre_adj[V[i]].push_back({W[i], U[i]});
		deg[U[i]]++;
		deg[V[i]]++;
	}
	for (int i = 0; i < N; i++) {
		sort(pre_adj[i].begin(), pre_adj[i].end());
		tree[i].init(i, pre_adj[i]);
		bucket[deg[i]].push_back(i);
	}
	vector<long long> res(N);
	vector<int> bad;
	for (K = N - 1; K >= 0; K--) {
		for (auto u: bad) {
			flag[u] = false;
		}
		for (auto u: bad) {
			if (!flag[u]) {
				dfs(u, -1);
				res[K] += dp[u][0];
			}
		}
		for (auto u: bucket[K]) {
			for (auto e: pre_adj[u]) {
				int v = e.second;
				int w = e.first;
				if (is_bad[v]) {
					adj[u].push_back({v, w});
					adj[v].push_back({u, w});
					tree[u].update(lower_bound(pre_adj[u].begin(), pre_adj[u].end(), make_pair(w, v)) - pre_adj[u].begin());
					tree[v].update(lower_bound(pre_adj[v].begin(), pre_adj[v].end(), make_pair(w, u)) - pre_adj[v].begin());
				}
			}
			bad.push_back(u);
			is_bad[u] = true;
		}
	}
	return res;
}

Compilation message

roads.cpp: In member function 'long long int segtree::get(long long int)':
roads.cpp:30:15: error: no matching function for call to 'max(long long int&, int)'
   30 |   x = max(x, 0);
      |               ^
In file included from /usr/include/c++/10/vector:60,
                 from roads.h:1,
                 from roads.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:254:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::max(const _Tp&, const _Tp&)'
  254 |     max(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:254:5: note:   template argument deduction/substitution failed:
roads.cpp:30:15: note:   deduced conflicting types for parameter 'const _Tp' ('long long int' and 'int')
   30 |   x = max(x, 0);
      |               ^
In file included from /usr/include/c++/10/vector:60,
                 from roads.h:1,
                 from roads.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:300:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::max(const _Tp&, const _Tp&, _Compare)'
  300 |     max(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:300:5: note:   template argument deduction/substitution failed:
roads.cpp:30:15: note:   deduced conflicting types for parameter 'const _Tp' ('long long int' and 'int')
   30 |   x = max(x, 0);
      |               ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from roads.cpp:2:
/usr/include/c++/10/bits/stl_algo.h:3480:5: note: candidate: 'template<class _Tp> constexpr _Tp std::max(std::initializer_list<_Tp>)'
 3480 |     max(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3480:5: note:   template argument deduction/substitution failed:
roads.cpp:30:15: note:   mismatched types 'std::initializer_list<_Tp>' and 'long long int'
   30 |   x = max(x, 0);
      |               ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from roads.cpp:2:
/usr/include/c++/10/bits/stl_algo.h:3486:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::max(std::initializer_list<_Tp>, _Compare)'
 3486 |     max(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3486:5: note:   template argument deduction/substitution failed:
roads.cpp:30:15: note:   mismatched types 'std::initializer_list<_Tp>' and 'long long int'
   30 |   x = max(x, 0);
      |               ^