Submission #1043370

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1043370	2024-08-04T08:53:33 Z	javotaz	LOSTIKS (INOI20_lostiks)	C++17	Compilation error	0 ms	0 KB

Main

// In the Name of Allah

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

#pragma GCC optimize("Ofast,unroll-loops,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,avx,avx2,sse4.2,popcnt,tune=native")

typedef long long ll;

#define F first
#define S second
#define pii pair<int, int>
#define pb push_back
#define pp pop_back
#define all(x) x.begin(), x.end()

const int N = 1e6 + 12, M = 20, inf = 2e9 + 7;
vector<pii> g[N];
int n, s, t, par[N], dp[(1 << M) + 4][M], p[N], kd[N], bt[M], sz, pd[N], e[N];
pii f[2 * M + 2][2 * M + 2];
bool mrk[N];
vector<int> v, d;

void ip() {
	cin >> n >> s >> t;
	for (int i = 1; i < n; i++) {
		int u, v, w;
		cin >> u >> v >> w;
		g[u].pb({v, w});
		g[v].pb({u, w});
	}
}

void dfs(int u) {
	for (auto i: g[u])
		if (i.F != par[u]) { 
			par[i.F] = u;
			e[i.F] = e[u] + 1;
			if (i.S) {
				pd[i.F] = d.size(), d.pb(i.F), kd[i.F] = i.S;
				v.pb(u), v.pb(i.S);
			}
			dfs(i.F);
		}
}

void dfs2(int u, int rt, int h = 0, int mask = 0, int par = -1) {
	if (mrk[u])
		f[rt][p[u]] = {h, mask};
	for (auto i: g[u])
		if (i.F != par)
			dfs2(i.F, rt, h + 1, (i.S? (mask | (1 << pd[(e[u] < e[i.F])? i.F : u])) : mask), u);
}

void solve() {
	par[s] = s;
	dfs(s);
	v.pb(s), v.pb(t);
	sort(all(v));
	v.resize(unique(all(v)) - v.begin());
	for (int i = 0; i < v.size(); i++) 
		p[v[i]] = i, mrk[v[i]] = true;
	for (int i = 0; i < v.size(); i++)
		dfs2(v[i], i);
	memset(dp, 127, sizeof dp);
	int c = d.size();
	int ans = inf;
	for (int mask = 1; mask < (1 << c); ++mask) {
		sz = 0;
		for (char i = 0; i < c; i++)
			if ((mask >> i) & 1)
				bt[sz++] = i;
		for (char id1 = 0; id1 < sz; ++id1) {
			int i = bt[id1];
			int u = d[i], ku = kd[d[i]], x = mask ^ (1 << i);
			if (__builtin_popcount(mask) == 1) {
				if (f[p[s]][p[ku]].S == x && f[p[ku]][p[par[u]]].S == x)
					dp[mask][i] = f[p[s]][p[ku]].F + f[p[ku]][p[par[u]]].F;
			}
			else if ((f[p[ku]][p[par[u]]] | x) == x) {
				for (char id2 = 0; id2 < c; ++id2)
					if (id2 != id2) {
						char j = bt[id2];
						int v = d[bt[id2]];
						if ((f[p[par[v]]][p[ku]].S | x) == x)
							dp[mask][i] = min(dp[mask][i], dp[x][j] + f[p[par[v]]][p[ku]].F + f[p[ku]][p[par[u]]].F);
					}
			}
			if ((f[p[par[u]]][p[t]].S | mask) == mask)
				ans = min(ans, dp[mask][i] + f[p[par[u]]][p[t]].F);
		}
	}
	if (f[p[s]][p[t]].S == 0)
		ans = f[p[s]][p[t]].F;
	cout << ((ans == inf)? -1 : ans) << '\n';
}

int32_t main() {
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	ip(), solve();
	return 0;
}

Compilation message

Main.cpp: In function 'void solve()':
Main.cpp:62:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |  for (int i = 0; i < v.size(); i++)
      |                  ~~^~~~~~~~~~
Main.cpp:64:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |  for (int i = 0; i < v.size(); i++)
      |                  ~~^~~~~~~~~~
Main.cpp:75:15: warning: array subscript has type 'char' [-Wchar-subscripts]
   75 |    int i = bt[id1];
      |               ^~~
Main.cpp:81:34: error: no match for 'operator|' (operand types are 'std::pair<int, int>' and 'int')
   81 |    else if ((f[p[ku]][p[par[u]]] | x) == x) {
      |              ~~~~~~~~~~~~~~~~~~~ ^ ~
      |                                |   |
      |                                |   int
      |                                std::pair<int, int>
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:45,
                 from Main.cpp:3:
/usr/include/c++/10/cstddef:134:3: note: candidate: 'constexpr std::byte std::operator|(std::byte, std::byte)'
  134 |   operator|(byte __l, byte __r) noexcept
      |   ^~~~~~~~
/usr/include/c++/10/cstddef:134:18: note:   no known conversion for argument 1 from 'std::pair<int, int>' to 'std::byte'
  134 |   operator|(byte __l, byte __r) noexcept
      |             ~~~~~^~~
In file included 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 Main.cpp:3:
/usr/include/c++/10/bits/ios_base.h:87:3: note: candidate: 'constexpr std::_Ios_Fmtflags std::operator|(std::_Ios_Fmtflags, std::_Ios_Fmtflags)'
   87 |   operator|(_Ios_Fmtflags __a, _Ios_Fmtflags __b)
      |   ^~~~~~~~
/usr/include/c++/10/bits/ios_base.h:87:27: note:   no known conversion for argument 1 from 'std::pair<int, int>' to 'std::_Ios_Fmtflags'
   87 |   operator|(_Ios_Fmtflags __a, _Ios_Fmtflags __b)
      |             ~~~~~~~~~~~~~~^~~
/usr/include/c++/10/bits/ios_base.h:129:3: note: candidate: 'constexpr std::_Ios_Openmode std::operator|(std::_Ios_Openmode, std::_Ios_Openmode)'
  129 |   operator|(_Ios_Openmode __a, _Ios_Openmode __b)
      |   ^~~~~~~~
/usr/include/c++/10/bits/ios_base.h:129:27: note:   no known conversion for argument 1 from 'std::pair<int, int>' to 'std::_Ios_Openmode'
  129 |   operator|(_Ios_Openmode __a, _Ios_Openmode __b)
      |             ~~~~~~~~~~~~~~^~~
/usr/include/c++/10/bits/ios_base.h:169:3: note: candidate: 'constexpr std::_Ios_Iostate std::operator|(std::_Ios_Iostate, std::_Ios_Iostate)'
  169 |   operator|(_Ios_Iostate __a, _Ios_Iostate __b)
      |   ^~~~~~~~
/usr/include/c++/10/bits/ios_base.h:169:26: note:   no known conversion for argument 1 from 'std::pair<int, int>' to 'std::_Ios_Iostate'
  169 |   operator|(_Ios_Iostate __a, _Ios_Iostate __b)
      |             ~~~~~~~~~~~~~^~~
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:66,
                 from Main.cpp:3:
/usr/include/c++/10/bitset:1444:5: note: candidate: 'template<long unsigned int _Nb> std::bitset<_Nb> std::operator|(const std::bitset<_Nb>&, const std::bitset<_Nb>&)'
 1444 |     operator|(const bitset<_Nb>& __x, const bitset<_Nb>& __y) _GLIBCXX_NOEXCEPT
      |     ^~~~~~~~
/usr/include/c++/10/bitset:1444:5: note:   template argument deduction/substitution failed:
Main.cpp:81:36: note:   'std::pair<int, int>' is not derived from 'const std::bitset<_Nb>'
   81 |    else if ((f[p[ku]][p[par[u]]] | x) == x) {
      |                                    ^
In file included from /usr/include/c++/10/bits/shared_ptr_atomic.h:33,
                 from /usr/include/c++/10/memory:85,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:82,
                 from Main.cpp:3:
/usr/include/c++/10/bits/atomic_base.h:94:3: note: candidate: 'constexpr std::memory_order std::operator|(std::memory_order, std::__memory_order_modifier)'
   94 |   operator|(memory_order __m, __memory_order_modifier __mod)
      |   ^~~~~~~~
/usr/include/c++/10/bits/atomic_base.h:94:26: note:   no known conversion for argument 1 from 'std::pair<int, int>' to 'std::memory_order'
   94 |   operator|(memory_order __m, __memory_order_modifier __mod)
      |             ~~~~~~~~~~~~~^~~
In file included from /usr/include/c++/10/valarray:603,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:95,
                 from Main.cpp:3:
/usr/include/c++/10/bits/valarray_after.h:412:5: note: candidate: 'template<class _Dom1, class _Dom2> std::_Expr<std::__detail::_BinClos<std::__bitwise_or, std::_Expr, std::_Expr, _Dom1, _Dom2>, typename std::__fun<std::__bitwise_or, typename _Dom1::value_type>::result_type> std::operator|(const std::_Expr<_Dom1, typename _Dom1::value_type>&, const std::_Expr<_Dom2, typename _Dom2::value_type>&)'
  412 |     _DEFINE_EXPR_BINARY_OPERATOR(|, __bitwise_or)
      |     ^~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/10/bits/valarray_after.h:412:5: note:   template argument deduction/substitution failed:
Main.cpp:81:36: note:   'std::pair<int, int>' is not derived from 'const std::_Expr<_Dom1, typename _Dom1::value_type>'
   81 |    else if ((f[p[ku]][p[par[u]]] | x) == x) {
      |                                    ^
In file included from /usr/include/c++/10/valarray:603,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:95,
                 from Main.cpp:3:
/usr/include/c++/10/bits/valarray_after.h:412:5: note: candidate: 'template<class _Dom> std::_Expr<std::__detail::_BinClos<std::__bitwise_or, std::_Expr, std::_Constant, _Dom, typename _Dom::value_type>, typename std::__fun<std::__bitwise_or, typename _Dom1::value_type>::result_type> std::operator|(const std::_Expr<_Dom1, typename _Dom1::value_type>&, const typename _Dom::value_type&)'
  412 |     _DEFINE_EXPR_BINARY_OPERATOR(|, __bitwise_or)
      |     ^~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/10/bits/valarray_after.h:412:5: note:   template argument deduction/substitution failed:
Main.cpp:81:36: note:   'std::pair<int, int>' is not derived from 'const std::_Expr<_Dom1, typename _Dom1::value_type>'
   81 |    else if ((f[p[ku]][p[par[u]]] | x) == x) {
      |                                    ^
In file included from /usr/include/c++/10/valarray:603,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:95,
                 from Main.cpp:3:
/usr/include/c++/10/bits/valarray_after.h:412:5: note: candidate: 'template<class _Dom> std::_Expr<std::__detail::_BinClos<std::__bitwise_or, std::_Constant, std::_Expr, typename _Dom::value_type, _Dom>, typename std::__fun<std::__bitwise_or, typename _Dom1::value_type>::result_type> std::operator|(const typename _Dom::value_type&, const std::_Expr<_Dom1, typename _Dom1::value_type>&)'
  412 |     _DEFINE_EXPR_BINARY_OPERATOR(|, __bitwise_or)
      |     ^~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/10/bits/valarray_after.h:412:5: note:   template argument deduction/substitution failed:
Main.cpp:81:36: note:   mismatched types 'const std::_Expr<_Dom1, typename _Dom1::value_type>' and 'int'
   81 |    else if ((f[p[ku]][p[par[u]]] | x) == x) {
      |                                    ^
In file included from /usr/include/c++/10/valarray:603,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:95,
                 from Main.cpp:3:
/usr/include/c++/10/bits/valarray_after.h:412:5: note: candidate: 'template<class _Dom> std::_Expr<std::__detail::_BinClos<std::__bitwise_or, std::_Expr, std::_ValArray, _Dom, typename _Dom::value_type>, typename std::__fun<std::__bitwise_or, typename _Dom1::value_type>::result_type> std::operator|(const std::_Expr<_Dom1, typename _Dom1::value_type>&, const std::valarray<typename _Dom::value_type>&)'
  412 |     _DEFINE_EXPR_BINARY_OPERATOR(|, __bitwise_or)
      |     ^~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/10/bits/valarray_after.h:412:5: note:   template argument deduction/substitution failed:
Main.cpp:81:36: note:   'std::pair<int, int>' is not derived from 'const std::_Expr<_Dom1, typename _Dom1::value_type>'
   81 |    else if ((f[p[ku]][p[par[u]]] | x) == x) {
      |                                    ^
In file included from /usr/include/c++/10/valarray:603,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:95,
                 from Main.cpp:3:
/usr/include/c++/10/bits/valarray_after.h:412:5: note: candidate: 'template<class _Dom> std::_Expr<std::__detail::_BinClos<std::__bitwise_or, std::_ValArray, std::_Expr, typename _Dom::value_type, _Dom>, typename std::__fun<std::__bitwise_or, typename _Dom1::value_type>::result_type> std::operator|(const std::valarray<typename _Dom::value_type>&, const std::_Expr<_Dom1, typename _Dom1::value_type>&)'
  412 |     _DEFINE_EXPR_BINARY_OPERATOR(|, __bitwise_or)
      |     ^~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/10/bits/valarray_after.h:412:5: note:   template argument deduction/substitution failed:
Main.cpp:81:36: note:   mismatched types 'const std::_Expr<_Dom1, typename _Dom1::value_type>' and 'int'
   81 |    else if ((f[p[ku]][p[par[u]]] | x) == x) {
      |                                    ^
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:95,
                 from Main.cpp:3:
/usr/include/c++/10/valarray:1192:1: note: candidate: 'template<class _Tp> std::_Expr<std::__detail::_BinClos<std::__bitwise_or, std::_ValArray, std::_ValArray, _Tp, _Tp>, typename std::__fun<std::__bitwise_or, _Tp>::result_type> std::operator|(const std::valarray<_Tp>&, const std::valarray<_Tp>&)'
 1192 | _DEFINE_BINARY_OPERATOR(|, __bitwise_or)
      | ^~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/10/valarray:1192:1: note:   template argument deduction/substitution failed:
Main.cpp:81:36: note:   'std::pair<int, int>' is not derived from 'const std::valarray<_Tp>'
   81 |    else if ((f[p[ku]][p[par[u]]] | x) == x) {
      |                                    ^
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:95,
                 from Main.cpp:3:
/usr/include/c++/10/valarray:1192:1: note: candidate: 'template<class _Tp> std::_Expr<std::__detail::_BinClos<std::__bitwise_or, std::_ValArray, std::_Constant, _Tp, _Tp>, typename std::__fun<std::__bitwise_or, _Tp>::result_type> std::operator|(const std::valarray<_Tp>&, const typename std::valarray<_Tp>::value_type&)'
 1192 | _DEFINE_BINARY_OPERATOR(|, __bitwise_or)
      | ^~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/10/valarray:1192:1: note:   template argument deduction/substitution failed:
Main.cpp:81:36: note:   'std::pair<int, int>' is not derived from 'const std::valarray<_Tp>'
   81 |    else if ((f[p[ku]][p[par[u]]] | x) == x) {
      |                                    ^
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:95,
                 from Main.cpp:3:
/usr/include/c++/10/valarray:1192:1: note: candidate: 'template<class _Tp> std::_Expr<std::__detail::_BinClos<std::__bitwise_or, std::_Constant, std::_ValArray, _Tp, _Tp>, typename std::__fun<std::__bitwise_or, _Tp>::result_type> std::operator|(const typename std::valarray<_Tp>::value_type&, const std::valarray<_Tp>&)'
 1192 | _DEFINE_BINARY_OPERATOR(|, __bitwise_or)
      | ^~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/10/valarray:1192:1: note:   template argument deduction/substitution failed:
Main.cpp:81:36: note:   mismatched types 'const std::valarray<_Tp>' and 'int'
   81 |    else if ((f[p[ku]][p[par[u]]] | x) == x) {
      |                                    ^
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:105,
                 from Main.cpp:3:
/usr/include/c++/10/future:149:20: note: candidate: 'constexpr std::launch std::operator|(std::launch, std::launch)'
  149 |   constexpr launch operator|(launch __x, launch __y)
      |                    ^~~~~~~~
/usr/include/c++/10/future:149:37: note:   no known conversion for argument 1 from 'std::pair<int, int>' to 'std::launch'
  149 |   constexpr launch operator|(launch __x, launch __y)
      |                              ~~~~~~~^~~
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:127,
                 from Main.cpp:3:
/usr/include/c++/10/charconv:664:3: note: candidate: 'constexpr std::chars_format std::operator|(std::chars_format, std::chars_format)'
  664 |   operator|(chars_format __lhs, chars_format __rhs) noexcept
      |   ^~~~~~~~
/usr/include/c++/10/charconv:664:26: note:   no known conversion for argument 1 from 'std::pair<int, int>' to 'std::chars_format'
  664 |   operator|(chars_format __lhs, chars_format __rhs) noexcept
      |             ~~~~~~~~~~~~~^~~~~
Main.cpp:83:14: warning: self-comparison always evaluates to false [-Wtautological-compare]
   83 |      if (id2 != id2) {
      |          ~~~ ^~ ~~~
Main.cpp:84:19: warning: array subscript has type 'char' [-Wchar-subscripts]
   84 |       char j = bt[id2];
      |                   ^~~
Main.cpp:85:20: warning: array subscript has type 'char' [-Wchar-subscripts]
   85 |       int v = d[bt[id2]];
      |                    ^~~
Main.cpp:87:45: warning: array subscript has type 'char' [-Wchar-subscripts]
   87 |        dp[mask][i] = min(dp[mask][i], dp[x][j] + f[p[par[v]]][p[ku]].F + f[p[ku]][p[par[u]]].F);
      |                                             ^