| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 721482 | LittleCube | Bridges (APIO19_bridges) | C++17 | Compilation error | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define F first
#define S second
using namespace std;
const int B = 320;
int N, M, Q, u[100005], v[100005], d[100005], nd[100005], ans[100005], dsu[50005], rk[50005], vis[100005];
vector<pii> ops;
int find(int k)
{
return k == dsu[k] ? k : find(dsu[k]);
}
void merge(int x, int y)
{
x = find(x), y = find(y);
if(x == y)
return;
if(rk[x] < rk[y])
merge(y, x);
else
{
dsu[y] = x;
rk[x] += rk[y];
ops.emplace_back(pii(x, y));
}
}
void undo(int t)
{
while((int)ops.size() > t)
{
auto [x, y] = ops.back();
ops.pop_back();
dsu[y] = y, rk[x] -= rk[y];
}
}
void init()
{
for (int i = 1; i <= N; i++)
dsu[i] = i, rk[i] = 1;
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> N >> M;
for (int i = 1; i <= M; i++)
cin >> u[i] >> v[i] >> d[i];
cin >> Q;
for (int i = 1; i <= Q; i += B)
{
init();
for (int j = 1; j <= M; j++)
vis[j] = 0;
// solve Q = [i, i + B - 1]
vector<tuple<int, int, int>> change;
vector<int> out;
// d, i, 0: addedge
// d, i, q: query i (ans[q])
vector<tuple<int, int, int, int>> event;
for (int j = i; j <= min(Q, i + B - 1); j++)
{
int t, a, b;
cin >> t >> a >> b;
if(t == 1)
{
change.emplace_back(make_tuple(j, a, b));
vis[a] = 1;
}
else
event.emplace_back(make_tuple(-b, a, j));
}
for (int j = 1; j <= M; j++)
if(!vis[j])
event.emplace_back(make_tuple(-d[j], j, 0));
else
{
change.emplace_back(make_tuple(i - 1, j, d[j]));
out.emplace_back(j);
}
sort(event.begin(), event.end());
sort(change.begin(), change.end());
for (auto [d, j, q] : event)
{
//cerr << "event " << d << ' ' << t << ' ' << j << ' ' << q << '\n';
if(q == 0)
{
//cerr << "include " << j << '\n';
merge(u[j], v[j]);
}
else
{
int T = ops.size();
for (auto [tt, k, dd] : change)
if(tt <= q)
nd[k] = dd;
for (auto k : out)
if(nd[k] >= -d)
{
//cerr << "tmp include " << k << '\n';
merge(u[k], v[k]);
}
ans[q] = rk[find(j)];
undo(T);
}
}
for (auto [t, j, dd] : change)
d[j] = dd;
}
for (int i = 1; i <= Q; i++)
{
if(ans[i] > 0)
cout << ans[i] << '\n';
}
}
Compilation message (stderr)
bridges.cpp: In function 'int main()':
bridges.cpp:93:13: error: only 3 names provided for structured binding
93 | for (auto [d, j, q] : event)
| ^~~~~~~~~
bridges.cpp:93:13: note: while 'std::tuple<int, int, int, int>' decomposes into 4 elements
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 bridges.cpp:2:
/usr/include/c++/10/ext/new_allocator.h: In instantiation of 'void __gnu_cxx::new_allocator<_Tp>::construct(_Up*, _Args&& ...) [with _Up = std::tuple<int, int, int, int>; _Args = {std::tuple<int, int, int>}; _Tp = std::tuple<int, int, int, int>]':
/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 = std::tuple<int, int, int, int>; _Args = {std::tuple<int, int, int>}; _Tp = std::tuple<int, int, int, int>; std::allocator_traits<std::allocator<_CharT> >::allocator_type = std::allocator<std::tuple<int, int, int, int> >]'
/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 = {std::tuple<int, int, int>}; _Tp = std::tuple<int, int, int, int>; _Alloc = std::allocator<std::tuple<int, int, int, int> >; std::vector<_Tp, _Alloc>::reference = std::tuple<int, int, int, int>&]'
bridges.cpp:81:44: required from here
/usr/include/c++/10/ext/new_allocator.h:150:4: error: no matching function for call to 'std::tuple<int, int, int, int>::tuple(std::tuple<int, int, int>)'
150 | { ::new((void *)__p) _Up(std::forward<_Args>(__args)...); }
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/10/functional:54,
from /usr/include/c++/10/pstl/glue_algorithm_defs.h:13,
from /usr/include/c++/10/algorithm:74,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
from bridges.cpp:2:
/usr/include/c++/10/tuple:795:2: note: candidate: 'template<class _Alloc, class ... _UElements, bool _Valid, typename std::enable_if<std::tuple<int, int, int, int>::_TCC<_Valid>::__is_explicitly_constructible<_UElements ...>(), bool>::type <anonymous> > std::tuple<_Elements>::tuple(std::allocator_arg_t, const _Alloc&, std::tuple<_Args2 ...>&&) [with _Alloc = _Alloc; _UElements = {_UElements ...}; bool _Valid = _Valid; typename std::enable_if<std::tuple<_Elements>::_TCC<_Valid>::__is_explicitly_constructible<_UElements ...>(), bool>::type <anonymous> = <anonymous>; _Elements = {int, int, int, int}]'
795 | tuple(allocator_arg_t __tag, const _Alloc& __a,
| ^~~~~
/usr/include/c++/10/tuple:795:2: note: template argument deduction/substitution failed:
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 bridges.cpp:2:
/usr/include/c++/10/ext/new_allocator.h:150:4: note: candidate expects 3 arguments, 1 provided
150 | { ::new((void *)__p) _Up(std::forward<_Args>(__args)...); }
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/10/functional:54,
from /usr/include/c++/10/pstl/glue_algorithm_defs.h:13,
from /usr/include/c++/10/algorithm:74,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
from bridges.cpp:2:
/usr/include/c++/10/tuple:783:2: note: candidate: 'template<class _Alloc, class ... _UElements, bool _Valid, typename std::enable_if<std::tuple<int, int, int, int>::_TCC<_Valid>::__is_implicitly_constructible<_UElements ...>(), bool>::type <anonymous> > std::tuple<_Elements>::tuple(std::allocator_arg_t, const _Alloc&, std::tuple<_Args2 ...>&&) [with _Alloc = _Alloc; _UElements = {_UElements ...}; bool _Valid = _Valid; typename std::enable_if<std::tuple<_Elements>::_TCC<_Valid>::__is_implicitly_constructible<_UElements ...>(), bool>::type <anonymous> = <anonymous>; _Elements = {int, int, int, int}]'
783 | tuple(allocator_arg_t __tag, const _Alloc& __a,
| ^~~~~
/usr/include/c++/10/tuple:783:2: note: template argument deduction/substitution failed:
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 bridges.cpp:2:
/usr/include/c++/10/ext/new_allocator.h:150:4: note: candidate expects 3 arguments, 1 provided
150 | { ::new((void *)__p) _Up(std::forward<_Args>(__args)...); }
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/10/functional:54,
from /usr/include/c++/10/pstl/glue_algorithm_defs.h:13,
from /usr/include/c++/10/algorithm:74,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
from bridges.cpp:2:
/usr/include/c++/10/tuple:772:2: note: candidate: 'template<class _Alloc, class ... _UElements, bool _Valid, typename std::enable_if<std::tuple<int, int, int, int>::_TCC<_Valid>::__is_explicitly_constructible<const _UElements& ...>(), bool>::type <anonymous> > std::tuple<_Elements>::tuple(std::allocator_arg_t, const _Alloc&, const std::tuple<_Args2 ...>&) [with _Alloc = _Alloc; _UElements = {_UElements ...}; bool _Valid = _Valid; typename std::enable_if<std::tuple<_Elements>::_TCC<_Valid>::__is_explicitly_constructible<const _UElements& ...>(), bool>::type <anonymous> = <anonymous>; _Elements = {int, int, int, int}]'
772 | tuple(allocator_arg_t __tag, const _Alloc& __a,
| ^~~~~
/usr/include/c++/10/tuple:772:2: note: template argument deduction/substitution failed:
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 bridges.cpp:2:
/usr/include/c++/10/ext/new_allocator.h:150:4: note: candidate expects 3 arguments, 1 provided
150 | { ::new((void *)__p) _Up(std::forward<_Args>(__args)...); }
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/10/functional:54,
from /usr/include/c++/10/pstl/glue_algorithm_defs.h:13,
from /usr/include/c++/10/algorithm:74,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
from bridges.cpp:2:
/usr/include/c++/10/tuple:760:2: note: candidate: 'template<class _Alloc, class ... _UElements, bool _Valid, typename std::enable_if<std::tuple<int, int, int, int>::_TCC<_Valid>::__is_implicitly_constructible<const _UElements& ...>(), bool>::type <anonymous> > std::tuple<_Elements>::tuple(std::allocator_arg_t, const _Alloc&, const std::tuple<_Args2 ...>&) [with _Alloc = _Alloc; _UElements = {_UElements ...}; bool _Valid = _Valid; typename std::enable_if<std::tuple<_Elements>::_TCC<_Valid>::__is_implicitly_constructible<const _UElements& ...>(), bool>::type <anonymous> = <anonymous>; _Elements = {int, int, int, int}]'
760 | tuple(allocator_arg_t __tag, const _Alloc& __a,
| ^~~~~
/usr/include/c++/10/tuple:760:2: note: template argument deduction/substitution failed:
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 bridges.cpp:2:
/usr/include/c++/10/ext/new_allocator.h:150:4: note: candidate expects 3 arguments, 1 provided
150 | { ::new((void *)__p) _Up(std::forward<_Args>(__args)...); }
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/10/functional:54,
from /usr/include/c++/10/pstl/glue_algorithm_defs.h:13,
from /usr/include/c++/10/algorithm:74,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
from bridges.cpp:2:
/usr/include/c++/10/tuple:752:2: note: candidate: 'template<class _Alloc> std::tuple<_Elements>::tuple(std::allocator_arg_t, const _Alloc&, std::tuple<_Elements>&&) [with _Alloc = _Alloc; _Elements = {int, int, int, int}]'
752 | tuple(allocator_arg_t __tag, const _Alloc& __a, tuple&& __in)
| ^~~~~
/usr/include/c++/10/tuple:752:2: note: template argument deduction/substitution failed:
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 bridges.cpp:2:
/usr/include/c++/10/ext/new_allocator.h:150:4: note: candidate expects 3 arguments, 1 provided
150 | { ::new((void *)__p) _Up(std::forward<_Args>(__args)...); }
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/10/functional:54,
from /usr/include/c++/10/pstl/glue_algorithm_defs.h:13,
from /usr/include/c++/10/algorithm:74,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
from bridges.cpp:2:
/usr/include/c++/10/tuple:747:2: note: candidate: 'template<class _Alloc> std::tuple<_Elements>::tuple(std::allocator_arg_t, const _Alloc&, const std::tuple<_Elements>&) [with _Alloc = _Alloc; _Elements = {int, int, int, int}]'
747 | tuple(allocator_arg_t __tag, const _Alloc& __a, const tuple& __in)
| ^~~~~
/usr/include/c++/10/tuple:747:2: note: template argument deduction/substitution failed:
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 bridges.cpp:2:
/usr/include/c++/10/ext/new_allocator.h:150:4: note: candidate expects 3 arguments, 1 provided
150 | { ::new((void *)__p) _Up(std::forward<_Args>(__args)...); }
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/10/functional:54,
from /usr/include/c++/10/pstl/glue_algorithm_defs.h:13,
from /usr/include/c++/10/algorithm:74,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
from bridges.cpp:2:
/usr/include/c++/10/tuple:740:2: note: candidate: 'template<class _Alloc, class ... _UElements, bool _Valid, typename std::enable_if<std::tuple<int, int, int, int>::_TCC<_Valid>::__is_explicitly_constructible<_UElements ...>(), bool>::type <anonymous> > std::tuple<_Elements>::tuple(std::allocator_arg_t, const _Alloc&, _UElements&& ...) [with _Alloc = _Alloc; _UElements = {_UElements ...}; bool _Valid = _Valid; typename std::enable_if<std::tuple<_Elements>::_TCC<_Valid>::__is_explicitly_constructible<_UElements ...>(), bool>::type <anonymous> = <anonymous>; _Elements = {int, int, int, int}]'
740 | tuple(allocator_arg_t __tag, const _Alloc& __a,
| ^~~~~
/usr/include/c++/10/tuple:740:2: note: template argument deduction/substitution failed:
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 bridges.cpp:2:
/usr/include/c++/10/ext/new_allocator.h:150:4: note: candidate expects at least 2 arguments, 1 provided
150 | { ::new((void *)__p) _Up(std::forward<_Args>(__args)...); }
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/10/functional:54,
from /usr/include/c++/10/pstl/glue_algorithm_defs.h:13,
from /usr/include/c++/10/algorithm:74,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
from bridges.cpp:2:
/usr/include/c++/10/tuple:730:2: note: candidate: 'template<class _Alloc, class ... _UElements, bool _Valid, typename std::enable_if<std::tuple<int, int, int, int>::_TCC<_Valid>::__is_implicitly_constructible<_UElements ...>(), bool>::type <anonymous> > std::tuple<_Elements>::tuple(std::allocator_arg_t, const _Alloc&, _UElements&& ...) [with _Alloc = _Alloc; _UElements = {_UElements ...}; bool _Valid = _Valid; typename std::enable_if<std::tuple<_Elements>::_TCC<_Valid>::__is_implicitly_constructible<_UElements ...>(), bool>::type <anonymous> = <anonymous>; _Elements = {int, int, int, int}]'
730 | tuple(allocator_arg_t __tag, const _Alloc& __a,
| ^~~~~
/usr/include/c++/10/tuple:730:2: note: template argument deduction/substitution failed:
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 bridges.cpp:2:
/usr/include/c++/10/ext/new_allocator.h:150:4: note: candidate expects at least 2 arguments, 1 provided
150 | { ::new((void *)__p) _Up(std::forward<_Args>(__args)...); }
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/10/functional:54,
from /usr/include/c++/10/pstl/glue_algorithm_defs.h:13,
from /usr/include/c++/10/algorithm:74,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
from bridges.cpp:2:
/usr/include/c++/10/tuple:722:2: note: candidate: 'template<class _Alloc, bool _NotEmpty, typename std::enable_if<std::tuple<int, int, int, int>::_TCC<_Valid>::__is_explicitly_constructible<const int&, const int&, const int&, const int&>(), bool>::type <anonymous> > std::tuple<_Elements>::tuple(std::allocator_arg_t, const _Alloc&, const _Elements& ...) [with _Alloc = _Alloc; bool _NotEmpty = _NotEmpty; typename std::enable_if<std::tuple<_Elements>::_TCC<_Valid>::__is_explicitly_constructible<const _Elements& ...>(), bool>::type <anonymous> = <anonymous>; _Elements = {int, int, int, int}]'
722 | tuple(allocator_arg_t __tag, const _Alloc& __a,
| ^~~~~
/usr/include/c++/10/tuple:722:2: note: template argument deduction/substitution failed:
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,