Submission #3399340


Source Code Expand

Copy
#include <bits/stdc++.h>

#ifdef NON_SUBMIT
#define TEST(n) (n)
#else
#define TEST(n) ((void)0)
#endif

using namespace std;

pair<int, int> tree[1 << 18];

void set_tree(int n, int v, int bit = 1, int s = 1, int e = 100000)
{
	int m = (s + e) >> 1;
	if (s == e) {
		tree[bit] = { v,n };
		return;
	}
	if (n <= m) {
		set_tree(n, v, 2 * bit, s, m);
	}
	else {
		set_tree(n, v, 2 * bit + 1, m + 1, e);
	}
	tree[bit] = max(tree[2 * bit], tree[2 * bit + 1]);
}

int get_value(int n)
{
	int bit = 1, s = 1, e = 100000;
	while (s < e) {
		int m = (s + e) >> 1;
		if (n <= m) {
			bit = 2 * bit;
			e = m;
		}
		else {
			bit = 2 * bit + 1;
			s = m + 1;
		}
	}
	return tree[bit].first;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	TEST(freopen("input.txt", "r", stdin));
	TEST(freopen("output.txt", "w", stdout));
	int N;
	long long ans = 0;
	priority_queue<tuple<int, int, int>> Q;
	cin >> N;
	for (int i = 1; i <= N; i++) {
		int A, B;
		cin >> A >> B;
		Q.push(make_tuple(-A, -B, i));
		set_tree(i, B);
	}
	while (!Q.empty()) {
		int v, idx, temp;
		tie(v, temp, idx) = Q.top();
		Q.pop();
		v = -v;
		if (temp = get_value(idx)) {
			set_tree(idx, 0);
			if (tree[1].first) {
				ans += min(tree[1].first, v);
			}
			else {
				ans += min(v, temp);
			}
			set_tree(tree[1].second, temp);
			Q.push({ -v,-temp,idx });
		}
	}
	cout << ans << '\n';
	return 0;
}

Submission Info

Submission Time
Task C - Min Cost Cycle
User Lawali
Language C++14 (GCC 5.4.1)
Score 0
Code Size 1477 Byte
Status

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:76:27: error: converting to ‘std::priority_queue<std::tuple<int, int, int> >::value_type {aka std::tuple<int, int, int>}’ from initializer list would use explicit constructor ‘constexpr std::tuple< <template-parameter-1-1> >::tuple(_UElements&& ...) [with _UElements = {int, int, int&}; <template-parameter-2-2> = void; _Elements = {int, int, int}]’
    Q.push({ -v,-temp,idx });
                           ^