| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1084106 | QwertyPi | 다리 (APIO19_bridges) | C++14 | 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.
#include <bits/stdc++.h>
using namespace std;
struct edge{
int u, v, w; bool ban;
};
struct query{
int t, a, b;
};
const int BLOCK = 400;
const int N = 1.1e5 + 11;
int ans[N]; bool ban[N];
struct DSU{
int dsu[N], sz[N];
vector<pair<int, int>> stmp;
DSU() { iota(dsu, dsu + N, 0), fill(sz, sz + N, 1); }
int f(int x) { return x == dsu[x] ? x : f(dsu[x]); }
void g(int x, int y) {
x = f(x), y = f(y);
if (x == y) return void(stmp.push_back({-1, -1}));
if (sz[x] > sz[y]) swap(x, y);
dsu[x] = y; sz[y] += sz[x];
stmp.push_back({x, y});
}
void rollback() {
assert(!stmp.empty());
auto [x, y] = stmp.back(); stmp.pop_back();
sz[y] -= sz[x]; dsu[x] = x;
}
} dsu;
int main() {
fill(ans, ans + N, -1);
cin.tie(0)->sync_with_stdio(false);
int n, m; cin >> n >> m;
vector<edge> E(1);
for (int i = 0; i < m; i++) {
int u, v, w; cin >> u >> v >> w;
E.push_back({u, v, w});
}
sort(E.begin(), E.end(), [](auto x, auto y){
return x.w < y.w;
});
int q; cin >> q;
vector<query> Q;
for (int i = 0; i < q; i++) {
int t; cin >> t;
int a, b; cin >> a >> b;
Q.push_back({t, a, b});
}
while (Q.size() % BLOCK != 0) {
Q.push_back({1, 0, 0});
}
assert(E.size() == m + 1);
for (int i = 0; i < Q.size(); i += BLOCK) {
auto upd_edge = [&] (bool state) {
for (int j = i; j < i + BLOCK; j++) {
auto [t, a, b] = Q[j];
if (t == 1) {
ban[a] = state;
}
}
};
upd_edge(true);
vector<query> C;
for (int j = i; j < i + BLOCK; j++) {
auto [t, a, b] = Q[j];
if (t == 2) {
C.push_back({j, a, b});
}
}
sort(C.begin(), C.end());
upd_edge(false);
for (int j = i; j < i + BLOCK; j++) {
auto [t, a, b] = Q[j];
if (t == 1) {
E[a].w = b;
}
}
}
for (int i = 0; i < Q.size(); i++) {
if (Q[i].t == 2) {
cout << ans[i] << '\n';
}
}
return 0;
}
Compilation message (stderr)
bridges.cpp: In member function 'void DSU::rollback()':
bridges.cpp:30:8: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
30 | auto [x, y] = stmp.back(); stmp.pop_back();
| ^
In file included from /usr/include/c++/10/cassert:44,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
from bridges.cpp:1:
bridges.cpp: In function 'int main()':
bridges.cpp:60:18: warning: comparison of integer expressions of different signedness: 'std::vector<edge>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
60 | assert(E.size() == m + 1);
| ~~~~~~~~~^~~~~~~~
bridges.cpp:62:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
62 | for (int i = 0; i < Q.size(); i += BLOCK) {
| ~~^~~~~~~~~~
bridges.cpp: In lambda function:
bridges.cpp:66:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
66 | auto [t, a, b] = Q[j];
| ^
bridges.cpp: In function 'int main()':
bridges.cpp:76:9: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
76 | auto [t, a, b] = Q[j];
| ^
bridges.cpp:85:9: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
85 | auto [t, a, b] = Q[j];
| ^
bridges.cpp:92:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
92 | for (int i = 0; i < Q.size(); i++) {
| ~~^~~~~~~~~~
In file included from /usr/include/c++/10/bits/stl_algobase.h:71,
from /usr/include/c++/10/bits/char_traits.h:39,
from /usr/include/c++/10/ios:40,
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:1:
/usr/include/c++/10/bits/predefined_ops.h: In instantiation of 'constexpr bool __gnu_cxx::__ops::_Iter_less_iter::operator()(_Iterator1, _Iterator2) const [with _Iterator1 = __gnu_cxx::__normal_iterator<query*, std::vector<query> >; _Iterator2 = __gnu_cxx::__normal_iterator<query*, std::vector<query> >]':
/usr/include/c++/10/bits/stl_algo.h:82:17: required from 'void std::__move_median_to_first(_Iterator, _Iterator, _Iterator, _Iterator, _Compare) [with _Iterator = __gnu_cxx::__normal_iterator<query*, std::vector<query> >; _Compare = __gnu_cxx::__ops::_Iter_less_iter]'
/usr/include/c++/10/bits/stl_algo.h:1924:34: required from '_RandomAccessIterator std::__unguarded_partition_pivot(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<query*, std::vector<query> >; _Compare = __gnu_cxx::__ops::_Iter_less_iter]'
/usr/include/c++/10/bits/stl_algo.h:1958:38: required from 'void std::__introsort_loop(_RandomAccessIterator, _RandomAccessIterator, _Size, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<query*, std::vector<query> >; _Size = long int; _Compare = __gnu_cxx::__ops::_Iter_less_iter]'
/usr/include/c++/10/bits/stl_algo.h:1974:25: required from 'void std::__sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<query*, std::vector<query> >; _Compare = __gnu_cxx::__ops::_Iter_less_iter]'
/usr/include/c++/10/bits/stl_algo.h:4859:18: required from 'void std::sort(_RAIter, _RAIter) [with _RAIter = __gnu_cxx::__normal_iterator<query*, std::vector<query> >]'
bridges.cpp:81:26: required from here
/usr/include/c++/10/bits/predefined_ops.h:43:23: error: no match for 'operator<' (operand types are 'query' and 'query')
43 | { return *__it1 < *__it2; }
| ~~~~~~~^~~~~~~~
In file included from /usr/include/c++/10/bits/stl_algobase.h:67,
from /usr/include/c++/10/bits/char_traits.h:39,
from /usr/include/c++/10/ios:40,
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:1:
/usr/include/c++/10/bits/stl_iterator.h:1096:5: note: candidate: 'template<class _IteratorL, class _IteratorR, class _Container> bool __gnu_cxx::operator<(const __gnu_cxx::__normal_iterator<_IteratorL, _Container>&, const __gnu_cxx::__normal_iterator<_IteratorR, _Container>&)'
1096 | operator<(const __normal_iterator<_IteratorL, _Container>& __lhs,
| ^~~~~~~~
/usr/include/c++/10/bits/stl_iterator.h:1096:5: note: template argument deduction/substitution failed:
In file included from /usr/include/c++/10/bits/stl_algobase.h:71,
from /usr/include/c++/10/bits/char_traits.h:39,
from /usr/include/c++/10/ios:40,
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:1:
/usr/include/c++/10/bits/predefined_ops.h:43:23: note: 'query' is not derived from 'const __gnu_cxx::__normal_iterator<_IteratorL, _Container>'
43 | { return *__it1 < *__it2; }
| ~~~~~~~^~~~~~~~
In file included from /usr/include/c++/10/bits/stl_algobase.h:67,
from /usr/include/c++/10/bits/char_traits.h:39,
from /usr/include/c++/10/ios:40,
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:1:
/usr/include/c++/10/bits/stl_iterator.h:1104:5: note: candidate: 'template<class _Iterator, class _Container> bool __gnu_cxx::operator<(const __gnu_cxx::__normal_iterator<_Iterator, _Container>&, const __gnu_cxx::__normal_iterator<_Iterator, _Container>&)'
1104 | operator<(const __normal_iterator<_Iterator, _Container>& __lhs,
| ^~~~~~~~
/usr/include/c++/10/bits/stl_iterator.h:1104:5: note: template argument deduction/substitution failed:
In file included from /usr/include/c++/10/bits/stl_algobase.h:71,
from /usr/include/c++/10/bits/char_traits.h:39,
from /usr/include/c++/10/ios:40,
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:1:
/usr/include/c++/10/bits/predefined_ops.h:43:23: note: 'query' is not derived from 'const __gnu_cxx::__normal_iterator<_Iterator, _Container>'
43 | { return *__it1 < *__it2; }
| ~~~~~~~^~~~~~~~
/usr/include/c++/10/bits/predefined_ops.h: In instantiation of 'bool __gnu_cxx::__ops::_Val_less_iter::operator()(_Value&, _Iterator) const [with _Value = query; _Iterator = __gnu_cxx::__normal_iterator<query*, std::vector<query> >]':
/usr/include/c++/10/bits/stl_algo.h:1826:20: required from 'void std::__unguarded_linear_insert(_RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<query*, std::vector<query> >; _Compare = __gnu_cxx::__ops::_Val_less_iter]'
/usr/include/c++/10/bits/stl_algo.h:1854:36: required from 'void std::__insertion_sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<query*, std::vector<query> >; _Compare = __gnu_cxx::__ops::_Iter_less_iter]'
/usr/include/c++/10/bits/stl_algo.h:1886:25: required from 'void std::__final_insertion_sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<query*, std::vector<query> >; _Compare = __gnu_cxx::__ops::_Iter_less_iter]'
/usr/include/c++/10/bits/stl_algo.h:1977:31: required from 'void std::__sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<query*, std::vector<query> >; _Compare = __gnu_cxx::__ops::_Iter_less_iter]'
/usr/include/c++/10/bits/stl_algo.h:4859:18: required from 'void std::sort(_RAIter, _RAIter) [with _RAIter = __gnu_cxx::__normal_iterator<query*, std::vector<query> >]'
bridges.cpp:81:26: required from here
/usr/include/c++/10/bits/predefined_ops.h:96:22: error: no match for 'operator<' (operand types are 'query' and 'query')
96 | { return __val < *__it; }
| ~~~~~~^~~~~~~
In file included from /usr/include/c++/10/bits/stl_algobase.h:67,
from /usr/include/c++/10/bits/char_traits.h:39,
from /usr/include/c++/10/ios:40,
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:1:
/usr/include/c++/10/bits/stl_iterator.h:1096:5: note: candidate: 'template<class _IteratorL, class _IteratorR, class _Container> bool __gnu_cxx::operator<(const __gnu_cxx::__normal_iterator<_IteratorL, _Container>&, const __gnu_cxx::__normal_iterator<_IteratorR, _Container>&)'
1096 | operator<(const __normal_iterator<_IteratorL, _Container>& __lhs,
| ^~~~~~~~
/usr/include/c++/10/bits/stl_iterator.h:1096:5: note: template argument deduction/substitution failed:
In file included from /usr/include/c++/10/bits/stl_algobase.h:71,
from /usr/include/c++/10/bits/char_traits.h:39,
from /usr/include/c++/10/ios:40,
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:1:
/usr/include/c++/10/bits/predefined_ops.h:96:22: note: 'query' is not derived from 'const __gnu_cxx::__normal_iterator<_IteratorL, _Container>'
96 | { return __val < *__it; }
| ~~~~~~^~~~~~~
In file included from /usr/include/c++/10/bits/stl_algobase.h:67,
from /usr/include/c++/10/bits/char_traits.h:39,
from /usr/include/c++/10/ios:40,
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:1:
/usr/include/c++/10/bits/stl_iterator.h:1104:5: note: candidate: 'template<class _Iterator, class _Container> bool __gnu_cxx::operator<(const __gnu_cxx::__normal_iterator<_Iterator, _Container>&, const __gnu_cxx::__normal_iterator<_Iterator, _Container>&)'
1104 | operator<(const __normal_iterator<_Iterator, _Container>& __lhs,
| ^~~~~~~~
/usr/include/c++/10/bits/stl_iterator.h:1104:5: note: template argument deduction/substitution failed:
In file included from /usr/include/c++/10/bits/stl_algobase.h:71,
from /usr/include/c++/10/bits/char_traits.h:39,
from /usr/include/c++/10/ios:40,
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:1:
/usr/include/c++/10/bits/predefined_ops.h:96:22: note: 'query' is not derived from 'const __gnu_cxx::__normal_iterator<_Iterator, _Container>'
96 | { return __val < *__it; }
| ~~~~~~^~~~~~~
/usr/include/c++/10/bits/predefined_ops.h: In instantiation of 'bool __gnu_cxx::__ops::_Iter_less_val::operator()(_Iterator, _Value&) const [with _Iterator = __gnu_cxx::__normal_iterator<query*, std::vector<query> >; _Value = query]':
/usr/include/c++/10/bits/stl_heap.h:139:48: required from 'void std::__push_heap(_RandomAccessIterator, _Distance, _Distance, _Tp, _Compare&) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<query*, std::vector<query> >; _Distance = long int; _Tp = query; _Compare = __gnu_cxx::__ops::_Iter_less_val]'
/usr/include/c++/10/bits/stl_heap.h:246:23: required from 'void std::__adjust_heap(_RandomAccessIterator, _Distance, _Distance, _Tp, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<query*, std::vector<query> >; _Distance = long int; _Tp = query; _Compare = __gnu_cxx::__ops::_Iter_less_iter]'
/usr/include/c++/10/bits/stl_heap.h:355:22: required from 'void std::__make_heap(_RandomAccessIterator, _RandomAccessIterator, _Compare&) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<query*, std::vector<query> >; _Compare = __gnu_cxx::__ops::_Iter_less_iter]'
/usr/include/c++/10/bits/stl_algo.h:1666:23: required from 'void std::__heap_select(_RandomAccessIterator, _RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<query*, std::vector<query> >; _Compare = __gnu_cxx::__ops::_Iter_less_iter]'
/usr/include/c++/10/bits/stl_algo.h:1937:25: required from 'void std::__partial_sort(_RandomAccessIterator, _RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<query*, std::vector<query> >; _Compare = __gnu_cxx::__ops::_Iter_less_iter]'
/usr/include/c++/10/bits/stl_algo.h:1953:27: required from 'void std::__introsort_loop(_RandomAccessIterator, _RandomAccessIterator, _Size, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<query*, std::vector<query> >; _Size = long int; _Compare = __gnu_cxx::__ops::_Iter_less_iter]'
/usr/include/c++/10/bits/stl_algo.h:1974:25: required from 'void std::__sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<query*, std::vector<query> >; _Compare = __gnu_cxx::__ops::_Iter_less_iter]'
/usr/include/c++/10/bits/stl_algo.h:4859:18: required from 'void std::sort(_RAIter, _RAIter) [with _RAIter = __gnu_cxx::__normal_iterator<query*, std::vector<query> >]'
bridges.cpp:81:26: required from here
/usr/include/c++/10/bits/predefined_ops.h:67:22: error: no match for 'operator<' (operand types are 'query' and 'query')
67 | { return *__it < __val; }
| ~~~~~~^~~~~~~
In file included from /usr/include/c++/10/bits/stl_algobase.h:67,
from /usr/include/c++/10/bits/char_traits.h:39,
from /usr/include/c++/10/ios:40,
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:1:
/usr/include/c++/10/bits/stl_iterator.h:1096:5: note: candidate: 'template<class _IteratorL, class _IteratorR, class _Container> bool __gnu_cxx::operator<(const __gnu_cxx::__normal_iterator<_IteratorL, _Container>&, const __gnu_cxx::__normal_iterator<_IteratorR, _Container>&)'
1096 | operator<(const __normal_iterator<_IteratorL, _Container>& __lhs,
| ^~~~~~~~
/usr/include/c++/10/bits/stl_iterator.h:1096:5: note: template argument deduction/substitution failed:
In file included from /usr/include/c++/10/bits/stl_algobase.h:71,
from /usr/include/c++/10/bits/char_traits.h:39,
from /usr/include/c++/10/ios:40,
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:1:
/usr/include/c++/10/bits/predefined_ops.h:67:22: note: 'query' is not derived from 'const __gnu_cxx::__normal_iterator<_IteratorL, _Container>'
67 | { return *__it < __val; }
| ~~~~~~^~~~~~~
In file included from /usr/include/c++/10/bits/stl_algobase.h:67,
from /usr/include/c++/10/bits/char_traits.h:39,
from /usr/include/c++/10/ios:40,
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:1:
/usr/include/c++/10/bits/stl_iterator.h:1104:5: note: candidate: 'template<class _Iterator, class _Container> bool __gnu_cxx::operator<(const __gnu_cxx::__normal_iterator<_Iterator, _Container>&, const __gnu_cxx::__normal_iterator<_Iterator, _Container>&)'
1104 | operator<(const __normal_iterator<_Iterator, _Container>& __lhs,
| ^~~~~~~~
/usr/include/c++/10/bits/stl_iterator.h:1104:5: note: template argument deduction/substitution failed:
In file included from /usr/include/c++/10/bits/stl_algobase.h:71,
from /usr/include/c++/10/bits/char_traits.h:39,
from /usr/include/c++/10/ios:40,
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:1:
/usr/include/c++/10/bits/predefined_ops.h:67:22: note: 'query' is not derived from 'const __gnu_cxx::__normal_iterator<_Iterator, _Container>'
67 | { return *__it < __val; }
| ~~~~~~^~~~~~~