Submission #796254

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
796254	2023-07-28T08:23:40 Z	GEN 이지후(#10112)	Security Guard (JOI23_guard)	C++17	Compilation error	0 ms	0 KB

guard

#include <bits/stdc++.h>
using namespace std;
using lint = long long;
using pi = array<lint, 2>;
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
const int MAXN = 200005;

// case tree:
// root with maximum
// anchor in parent
// using the guard from root, can do everything

struct disj {
	int pa[MAXN], mx[MAXN];
	void init(int n, lint *a) {
		iota(pa, pa + n + 1, 0);
		for (int i = 0; i < n; i++)
			mx[i] = a[i];
	}
	int find(int x) { return pa[x] = (pa[x] == x ? x : find(pa[x])); }
	int query(int x) { return mx[find(x)]; }
	bool uni(int p, int q) {
		p = find(p);
		q = find(q);
		if (p == q)
			return 0;
		pa[q] = p;
		mx[p] = min(mx[p], mx[q]);
		return 1;
	}
} disj;

using node = array<lint, 3>;
priority_queue<pi, vector<pi>, greater<pi>> pq[MAXN];
priority_queue<node, vector<node>, greater<node>> global;

vector<pi> gph[MAXN];
lint a[MAXN];

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n, m, q;
	cin >> n >> m >> q;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	vector<array<int, 3>> edges(m);
	for (auto &[x, s, e] : edges) {
		cin >> s >> e;
		s--;
		e--;
		x = a[s] + a[e];
	}
	sort(all(edges));
	disj.init(n, a);
	for (auto &[x, s, e] : edges) {
		if (disj.uni(s, e)) {
			pq[s].push({x, e});
			pq[e].push({x, s});
			global.push({x - a[s], s, a[s]}); // anticipated, from, truth check
			global.push({x - a[e], e, a[e]}); // anticipated, from, truth check
		}
	}
	disj.init(n, a);
	int rt = min_element(a, a + n) - a;
	lint tot = 1ll * a[rt] * (n - 2) + *max_element(a, a + n);
	vector<lint> ans(q + 1, tot);
	for (int i = n - 2; i >= 0; i--) {
		while (sz(global) && disj.query(global.top()[1]) != global.top()[2]) {
			global.pop();
		}
		assert(sz(global));
		int v = disj.find(global.top()[1]);
		auto tp = pq[v].top();
		tot += tp[0] - disj.query(v) - a[rt];
		if (i < sz(ans))
			ans[i] = tot;

		int w = tp[1];
		v = disj.find(v);
		w = disj.find(w);
		disj.uni(v, w); // pa[w] = v;
		if (sz(pq[w]) > sz(pq[v])) {
			swap(pq[w], pq[v]);
		}
		while (sz(pq[w])) {
			auto tp = pq[w].top();
			pq[w].pop();
			if (disj.find(tp[1]) == disj.find(v))
				continue;
			pq[v].push({x, tp[1]});
			global.push({x - disj.query(v), v, disj.query(v)});
		}
	}
	for (auto &x : ans)
		cout << x << "\n";
}

Compilation message

guard.cpp: In function 'int main()':
guard.cpp:94:16: error: 'x' was not declared in this scope
   94 |    pq[v].push({x, tp[1]});
      |                ^
guard.cpp:94:25: error: no matching function for call to 'std::priority_queue<std::array<long long int, 2>, std::vector<std::array<long long int, 2> >, std::greater<std::array<long long int, 2> > >::push(<brace-enclosed initializer list>)'
   94 |    pq[v].push({x, tp[1]});
      |                         ^
In file included from /usr/include/c++/10/queue:64,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:86,
                 from guard.cpp:1:
/usr/include/c++/10/bits/stl_queue.h:640:7: note: candidate: 'void std::priority_queue<_Tp, _Sequence, _Compare>::push(const value_type&) [with _Tp = std::array<long long int, 2>; _Sequence = std::vector<std::array<long long int, 2> >; _Compare = std::greater<std::array<long long int, 2> >; std::priority_queue<_Tp, _Sequence, _Compare>::value_type = std::array<long long int, 2>]'
  640 |       push(const value_type& __x)
      |       ^~~~
/usr/include/c++/10/bits/stl_queue.h:640:30: note:   no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'const value_type&' {aka 'const std::array<long long int, 2>&'}
  640 |       push(const value_type& __x)
      |            ~~~~~~~~~~~~~~~~~~^~~
/usr/include/c++/10/bits/stl_queue.h:648:7: note: candidate: 'void std::priority_queue<_Tp, _Sequence, _Compare>::push(std::priority_queue<_Tp, _Sequence, _Compare>::value_type&&) [with _Tp = std::array<long long int, 2>; _Sequence = std::vector<std::array<long long int, 2> >; _Compare = std::greater<std::array<long long int, 2> >; std::priority_queue<_Tp, _Sequence, _Compare>::value_type = std::array<long long int, 2>]'
  648 |       push(value_type&& __x)
      |       ^~~~
/usr/include/c++/10/bits/stl_queue.h:648:25: note:   no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'std::priority_queue<std::array<long long int, 2>, std::vector<std::array<long long int, 2> >, std::greater<std::array<long long int, 2> > >::value_type&&' {aka 'std::array<long long int, 2>&&'}
  648 |       push(value_type&& __x)
      |            ~~~~~~~~~~~~~^~~
guard.cpp:95:53: error: no matching function for call to 'std::priority_queue<std::array<long long int, 3>, std::vector<std::array<long long int, 3> >, std::greater<std::array<long long int, 3> > >::push(<brace-enclosed initializer list>)'
   95 |    global.push({x - disj.query(v), v, disj.query(v)});
      |                                                     ^
In file included from /usr/include/c++/10/queue:64,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:86,
                 from guard.cpp:1:
/usr/include/c++/10/bits/stl_queue.h:640:7: note: candidate: 'void std::priority_queue<_Tp, _Sequence, _Compare>::push(const value_type&) [with _Tp = std::array<long long int, 3>; _Sequence = std::vector<std::array<long long int, 3> >; _Compare = std::greater<std::array<long long int, 3> >; std::priority_queue<_Tp, _Sequence, _Compare>::value_type = std::array<long long int, 3>]'
  640 |       push(const value_type& __x)
      |       ^~~~
/usr/include/c++/10/bits/stl_queue.h:640:30: note:   no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'const value_type&' {aka 'const std::array<long long int, 3>&'}
  640 |       push(const value_type& __x)
      |            ~~~~~~~~~~~~~~~~~~^~~
/usr/include/c++/10/bits/stl_queue.h:648:7: note: candidate: 'void std::priority_queue<_Tp, _Sequence, _Compare>::push(std::priority_queue<_Tp, _Sequence, _Compare>::value_type&&) [with _Tp = std::array<long long int, 3>; _Sequence = std::vector<std::array<long long int, 3> >; _Compare = std::greater<std::array<long long int, 3> >; std::priority_queue<_Tp, _Sequence, _Compare>::value_type = std::array<long long int, 3>]'
  648 |       push(value_type&& __x)
      |       ^~~~
/usr/include/c++/10/bits/stl_queue.h:648:25: note:   no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'std::priority_queue<std::array<long long int, 3>, std::vector<std::array<long long int, 3> >, std::greater<std::array<long long int, 3> > >::value_type&&' {aka 'std::array<long long int, 3>&&'}
  648 |       push(value_type&& __x)
      |            ~~~~~~~~~~~~~^~~