Submission #535969

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
535969	2022-03-12T02:43:40 Z	dutinmeow	Swapping Cities (APIO20_swap)	C++17	Compilation error	0 ms	0 KB

swap

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

//#include "swap.h"

const int LOGN = 17;

vector<int> dep, val;
vector<bool> lin;
vector<array<int, LOGN>> anc;

void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
	vector<tuple<int, int, int>> E(M);
	for (int i = 0; i < M; i++) 
		E[i] = {U[i], V[i], W[i]};
	sort(E.begin(), E.end(), 
		[](const auto &a, const auto &b) {
			return get<2>(a) < get<2>(b);
		}
	);

	struct node { int par, val, siz; bool lin; };
	vector<node> T; T.reserve(N + M);
	vector<bool> ep(N);
	vector<int> rt(N);

	for (int i = 0; i < N; i++) {
		T.emplace_back(i, 0, 1, true);
		ep[i] = true;
		rt[i] = i;
	}

	for (auto [u, v, w] : E) {
		while (rt[u] != T[rt[u]].par)
			rt[u] = T[rt[u]].par;
		int up = rt[u];
		while (rt[v] != T[rt[v]].par)
			rt[v] = T[rt[v]].par;
		int vp = rt[v];

		int c = T.size();
		if (up != vp) {
			if (T[up].lin && T[vp].lin && ep[u] && ep[v]) {
				T[up].par = T[vp].par = c;
				T.emplace_back(c, w, T[up].siz + T[vp].siz, true);
				if (T[up].siz > 1)
					ep[u] = false;
				if (T[vp].siz > 1)
					ep[v] = false;
			} else {
				T[up].par = T[vp].par = T.size();
				T.emplace_back(c, w, T[up].siz + T[vp].siz, false);
			}
		} else if (T[up].lin) {
			T[up].par = c;
			T.emplace_back(c, w, T[up].siz + T[vp].siz, false);
		}

		/*
		cout << "edge " << u << ' ' << v << ' ' << w << '\n';
		for (int i = 0; i < T.size(); i++) 
			cout << i << " : " << T[i].par << ' ' << T[i].val << ' ' << (T[i].lin ? "line" : "not line") << '\n';
		cout << '\n';
		*/
	}

	int S = T.size();
	anc.resize(S);
	dep.resize(S);
	val.resize(S);
	lin.resize(S);
	vector<vector<int>> tree(S);
	for (int i = 0; i < S; i++) {
		anc[i][0] = T[i].par;
		val[i] = T[i].val;
		lin[i] = T[i].lin;
		if (i != T[i].par)
			tree[T[i].par].push_back(i);
	}
	for (int k = 1; k < LOGN; k++)
		for (int i = 0; i < S; i++)
			anc[i][k] = anc[anc[i][k - 1]][k - 1];

	const auto dfs = [&](const auto &self, int u) -> void {
		for (int v : tree[u]) {
			dep[v] = dep[u] + 1;
			self(self, v);
		}
	};

	for (int i = 0; i < S; i++) 
		if (i == T[i].par) {
			dep[i] = 0;
			dfs(dfs, i);
		}
}

int getMinimumFuelCapacity(int u, int v) {
	if (dep[u] > dep[v])
		swap(u, v);
	for (int k = LOGN - 1; k >= 0; k--)
		if ((dep[v] - dep[u]) >> k & 1)
			v = anc[v][k];
	//assert(dep[u] == dep[v]);
	if (u != v) {
		for (int k = LOGN - 1; k >= 0; k--)
			if (anc[u][k] != anc[v][k])
				u = anc[u][k], v = anc[v][k];
		u = anc[u][0], v = anc[v][0];
		if (u != v)
			return -1;
	}

	if (!lin[u]) 
		return val[u];
	for (int k = LOGN - 1; k >= 0; k--)
		if (lin[anc[u][k]])
			u = anc[u][k];
	u = anc[u][0];
	if (lin[u]) {
		return -1;
	} else {
		return val[u];
	}
}

Compilation message

In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/c++allocator.h:33,
                 from /usr/include/c++/10/bits/allocator.h:46,
                 from /usr/include/c++/10/string:41,
                 from /usr/include/c++/10/bits/locale_classes.h:40,
                 from /usr/include/c++/10/bits/ios_base.h:41,
                 from /usr/include/c++/10/ios:42,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from swap.cpp:1:
/usr/include/c++/10/ext/new_allocator.h: In instantiation of 'void __gnu_cxx::new_allocator<_Tp>::construct(_Up*, _Args&& ...) [with _Up = init(int, int, std::vector<int>, std::vector<int>, std::vector<int>)::node; _Args = {int&, int, int, bool}; _Tp = init(int, int, std::vector<int>, std::vector<int>, std::vector<int>)::node]':
/usr/include/c++/10/bits/alloc_traits.h:512:17:   required from 'static void std::allocator_traits<std::allocator<_CharT> >::construct(std::allocator_traits<std::allocator<_CharT> >::allocator_type&, _Up*, _Args&& ...) [with _Up = init(int, int, std::vector<int>, std::vector<int>, std::vector<int>)::node; _Args = {int&, int, int, bool}; _Tp = init(int, int, std::vector<int>, std::vector<int>, std::vector<int>)::node; std::allocator_traits<std::allocator<_CharT> >::allocator_type = std::allocator<init(int, int, std::vector<int>, std::vector<int>, std::vector<int>)::node>]'
/usr/include/c++/10/bits/vector.tcc:115:30:   required from 'std::vector<_Tp, _Alloc>::reference std::vector<_Tp, _Alloc>::emplace_back(_Args&& ...) [with _Args = {int&, int, int, bool}; _Tp = init(int, int, std::vector<int>, std::vector<int>, std::vector<int>)::node; _Alloc = std::allocator<init(int, int, std::vector<int>, std::vector<int>, std::vector<int>)::node>; std::vector<_Tp, _Alloc>::reference = init(int, int, std::vector<int>, std::vector<int>, std::vector<int>)::node&]'
swap.cpp:28:31:   required from here
/usr/include/c++/10/ext/new_allocator.h:150:4: error: new initializer expression list treated as compound expression [-fpermissive]
  150 |  { ::new((void *)__p) _Up(std::forward<_Args>(__args)...); }
      |    ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/10/ext/new_allocator.h:150:4: error: no matching function for call to 'init(int, int, std::vector<int>, std::vector<int>, std::vector<int>)::node::node(bool)'
swap.cpp:22:9: note: candidate: 'init(int, int, std::vector<int>, std::vector<int>, std::vector<int>)::node::node()'
   22 |  struct node { int par, val, siz; bool lin; };
      |         ^~~~
swap.cpp:22:9: note:   candidate expects 0 arguments, 1 provided
swap.cpp:22:9: note: candidate: 'constexpr init(int, int, std::vector<int>, std::vector<int>, std::vector<int>)::node::node(const init(int, int, std::vector<int>, std::vector<int>, std::vector<int>)::node&)'
swap.cpp:22:9: note:   no known conversion for argument 1 from 'bool' to 'const init(int, int, std::vector<int>, std::vector<int>, std::vector<int>)::node&'
swap.cpp:22:9: note: candidate: 'constexpr init(int, int, std::vector<int>, std::vector<int>, std::vector<int>)::node::node(init(int, int, std::vector<int>, std::vector<int>, std::vector<int>)::node&&)'
swap.cpp:22:9: note:   no known conversion for argument 1 from 'bool' to 'init(int, int, std::vector<int>, std::vector<int>, std::vector<int>)::node&&'
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/c++allocator.h:33,
                 from /usr/include/c++/10/bits/allocator.h:46,
                 from /usr/include/c++/10/string:41,
                 from /usr/include/c++/10/bits/locale_classes.h:40,
                 from /usr/include/c++/10/bits/ios_base.h:41,
                 from /usr/include/c++/10/ios:42,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from swap.cpp:1:
/usr/include/c++/10/ext/new_allocator.h: In instantiation of 'void __gnu_cxx::new_allocator<_Tp>::construct(_Up*, _Args&& ...) [with _Up = init(int, int, std::vector<int>, std::vector<int>, std::vector<int>)::node; _Args = {int&, int&, int, bool}; _Tp = init(int, int, std::vector<int>, std::vector<int>, std::vector<int>)::node]':
/usr/include/c++/10/bits/alloc_traits.h:512:17:   required from 'static void std::allocator_traits<std::allocator<_CharT> >::construct(std::allocator_traits<std::allocator<_CharT> >::allocator_type&, _Up*, _Args&& ...) [with _Up = init(int, int, std::vector<int>, std::vector<int>, std::vector<int>)::node; _Args = {int&, int&, int, bool}; _Tp = init(int, int, std::vector<int>, std::vector<int>, std::vector<int>)::node; std::allocator_traits<std::allocator<_CharT> >::allocator_type = std::allocator<init(int, int, std::vector<int>, std::vector<int>, std::vector<int>)::node>]'
/usr/include/c++/10/bits/vector.tcc:115:30:   required from 'std::vector<_Tp, _Alloc>::reference std::vector<_Tp, _Alloc>::emplace_back(_Args&& ...) [with _Args = {int&, int&, int, bool}; _Tp = init(int, int, std::vector<int>, std::vector<int>, std::vector<int>)::node; _Alloc = std::allocator<init(int, int, std::vector<int>, std::vector<int>, std::vector<int>)::node>; std::vector<_Tp, _Alloc>::reference = init(int, int, std::vector<int>, std::vector<int>, std::vector<int>)::node&]'
swap.cpp:45:53:   required from here
/usr/include/c++/10/ext/new_allocator.h:150:4: error: new initializer expression list treated as compound expression [-fpermissive]
  150 |  { ::new((void *)__p) _Up(std::forward<_Args>(__args)...); }
      |    ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/10/ext/new_allocator.h:150:4: error: no matching function for call to 'init(int, int, std::vector<int>, std::vector<int>, std::vector<int>)::node::node(bool)'
swap.cpp:22:9: note: candidate: 'init(int, int, std::vector<int>, std::vector<int>, std::vector<int>)::node::node()'
   22 |  struct node { int par, val, siz; bool lin; };
      |         ^~~~
swap.cpp:22:9: note:   candidate expects 0 arguments, 1 provided
swap.cpp:22:9: note: candidate: 'constexpr init(int, int, std::vector<int>, std::vector<int>, std::vector<int>)::node::node(const init(int, int, std::vector<int>, std::vector<int>, std::vector<int>)::node&)'
swap.cpp:22:9: note:   no known conversion for argument 1 from 'bool' to 'const init(int, int, std::vector<int>, std::vector<int>, std::vector<int>)::node&'
swap.cpp:22:9: note: candidate: 'constexpr init(int, int, std::vector<int>, std::vector<int>, std::vector<int>)::node::node(init(int, int, std::vector<int>, std::vector<int>, std::vector<int>)::node&&)'
swap.cpp:22:9: note:   no known conversion for argument 1 from 'bool' to 'init(int, int, std::vector<int>, std::vector<int>, std::vector<int>)::node&&'