Submission #1325115

#	Time	Username	Problem	Language	Result	Execution time	Memory
1325115		zwezdinv	Collapse (JOI18_collapse)	C++20	Compilation error	0 ms	0 KiB

collapse

#include<bits/stdc++.h>

using ll = long long;

struct DSU {
    std::vector<int> morgendorffer, sizeofcup;
    std::vector<std::pair<int&, int>> kevin;
    int toootal = 0;
    DSU() = default;
    DSU(int n) : toootal(n), morgendorffer(n), sizeofcup(n, 1) {
        std::iota(morgendorffer.begin(), morgendorffer.end(), 0);
    }
    int daria(int u) {
        while (u != morgendorffer[u]) u = morgendorffer[u];
        return u;
    }
    void jane(int u, int v) {
        u = daria(u), v = daria(v);
        if (u != v) {
            if (sizeofcup[u] > sizeofcup[v]) std::swap(u, v);
            kevin.emplace_back(&sizeofcup[u], sizeofcup[u]);
            sizeofcup[u] += sizeofcup[v];
            kevin.emplace_back(&morgendorffer[v], morgendorffer[v]);
            morgendorffer[v] = u;
            kevin.emplace_back(&toootal, toootal);
            --toootal;
        }
    }
    void brittany(int t) {
        while (kevin.size() > t) {
            kevin.back().first = kevin.back().second, kevin.pop_back();
        }
    }
};

std::vector<int> simulateCollapse(int n, std::vector<int> t, std::vector<int> x, std::vector<int> y, std::vector<int> w, std::vector<int> p) {
    struct Q {
        int l, r, x, y;
        Q() = default;
        Q(int l, int r, int x, int y) : l(l), r(r), x(x), y(y) {}
    };
    int m = t.size(), q = w.size();
    std::vector<Q> ques;
    std::map<std::pair<int, int>, int> time;
    for (int i = 0; i < m; ++i) {
        if (x[i] > y[i]) std::swap(x[i], y[i]);
        if (t[i] == 0) {
            time[{x[i], y[i]}] = i;
        } else {
            ques.emplace_back(time[{x[i], y[i]}], i, x[i], y[i]);
            time.erase({x[i], y[i]});
        }
    }
    for (auto [e, t] : time) {
        ques.emplace_back(t, q, e.first, e.second);
    }
    const int K = 317;
    std::vector<int> ans(q);
    for (int tl = 0; tl < q; tl += K) {
        int tr = std::min(q, tl + K);
        std::vector<Q> unsure;
        std::vector<std::vector<int64_t>> fst(n), fen(n);
        for (auto [l, r, x, y] : ques) {
            if (r <= tl || tr <= l) continue;
            if (l <= tl && tr <= r) {
                fst[x].push_back(y);
                fen[y].push_back(x);
            }
        }
        std::vector<int> timer(n);
        DSU suf(n), pref(n);
        for (int i = n - 1; i >= 0; --i) {
            timer[i] = suf.kevin.size();
            for (auto j : fst[i]) {
                suf.jane(i, j);
            }
        }
        std::vector<std::vector<int>> occ(n);
        for (int i = 0; i < q; ++i) {
            if (tl <= w[i] && w[i] < tr) {
                occ[p[i]].push_back(i);
            }
        }
        for (int i = 0; i < n; ++i) {
            suf.brittany(timer[i]);
            for (auto j : fen[i]) pref.jane(i, j);
            for (auto id : occ[i]) {
                int tpref = pref.kevin.size(), tsuf = suf.kevin.size();
                for (auto [l, r, x, y] : unsure) {
                    if (l <= w[id] && w[id] < r) {
                        if (y <= p[id]) pref.jane(x, y);
                        if (p[id] < x) suf.jane(x, y);
                    }
                }
                ans[id] = pref.toootal- (n - i - 1) + suf.toootal - (i + 1);
                pref.brittany(tpref);
                suf.brittany(tsuf);
            }
        }
    }
    return ans;
}

Compilation message (stderr)

In file included from /usr/include/c++/13/ext/alloc_traits.h:34,
                 from /usr/include/c++/13/bits/basic_string.h:39,
                 from /usr/include/c++/13/string:54,
                 from /usr/include/c++/13/bitset:52,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:52,
                 from collapse.cpp:1:
/usr/include/c++/13/bits/alloc_traits.h: In instantiation of 'static constexpr void std::allocator_traits<std::allocator<_CharT> >::construct(allocator_type&, _Up*, _Args&& ...) [with _Up = std::pair<int&, int>; _Args = {int*, int&}; _Tp = std::pair<int&, int>; allocator_type = std::allocator<std::pair<int&, int> >]':
/usr/include/c++/13/bits/vector.tcc:117:30:   required from 'constexpr std::vector<_Tp, _Alloc>::reference std::vector<_Tp, _Alloc>::emplace_back(_Args&& ...) [with _Args = {int*, int&}; _Tp = std::pair<int&, int>; _Alloc = std::allocator<std::pair<int&, int> >; reference = std::pair<int&, int>&]'
collapse.cpp:21:31:   required from here
/usr/include/c++/13/bits/alloc_traits.h:540:28: error: no matching function for call to 'construct_at(std::pair<int&, int>*&, int*, int&)'
  540 |           std::construct_at(__p, std::forward<_Args>(__args)...);
      |           ~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/13/bits/stl_iterator.h:85,
                 from /usr/include/c++/13/bits/stl_algobase.h:67,
                 from /usr/include/c++/13/algorithm:60,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:51:
/usr/include/c++/13/bits/stl_construct.h:94:5: note: candidate: 'template<class _Tp, class ... _Args> constexpr decltype (::new(void*(0)) _Tp) std::construct_at(_Tp*, _Args&& ...)'
   94 |     construct_at(_Tp* __location, _Args&&... __args)
      |     ^~~~~~~~~~~~
/usr/include/c++/13/bits/stl_construct.h:94:5: note:   template argument deduction/substitution failed:
/usr/include/c++/13/bits/stl_construct.h: In substitution of 'template<class _Tp, class ... _Args> constexpr decltype (::new(void*(0)) _Tp) std::construct_at(_Tp*, _Args&& ...) [with _Tp = std::pair<int&, int>; _Args = {int*, int&}]':
/usr/include/c++/13/bits/alloc_traits.h:540:21:   required from 'static constexpr void std::allocator_traits<std::allocator<_CharT> >::construct(allocator_type&, _Up*, _Args&& ...) [with _Up = std::pair<int&, int>; _Args = {int*, int&}; _Tp = std::pair<int&, int>; allocator_type = std::allocator<std::pair<int&, int> >]'
/usr/include/c++/13/bits/vector.tcc:117:30:   required from 'constexpr std::vector<_Tp, _Alloc>::reference std::vector<_Tp, _Alloc>::emplace_back(_Args&& ...) [with _Args = {int*, int&}; _Tp = std::pair<int&, int>; _Alloc = std::allocator<std::pair<int&, int> >; reference = std::pair<int&, int>&]'
collapse.cpp:21:31:   required from here
/usr/include/c++/13/bits/stl_construct.h:96:17: error: no matching function for call to 'std::pair<int&, int>::pair(int*, int&)'
   96 |     -> decltype(::new((void*)0) _Tp(std::declval<_Args>()...))
      |                 ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/13/bits/stl_algobase.h:64:
/usr/include/c++/13/bits/stl_pair.h:305:7: note: candidate: 'constexpr std::pair<_T1, _T2>::pair(const _T1&, const _T2&) requires  _S_constructible<const _T1&, const _T2&>() [with _T1 = int&; _T2 = int]' (near match)
  305 |       pair(const _T1& __x, const _T2& __y)
      |       ^~~~
/usr/include/c++/13/bits/stl_pair.h:305:7: note:   conversion of argument 1 would be ill-formed:
/usr/include/c++/13/bits/stl_construct.h:96:17: error: invalid conversion from 'int*' to 'int' [-fpermissive]
   96 |     -> decltype(::new((void*)0) _Tp(std::declval<_Args>()...))
      |                 ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
      |                 |
      |                 int*
/usr/include/c++/13/bits/stl_construct.h:96:17: error: cannot bind rvalue '(int)std::declval<int*>()' to 'int&'
/usr/include/c++/13/bits/stl_pair.h:354:9: note: candidate: 'template<class _U1, class _U2>  requires  _S_constructible<_U1, _U2>() && _S_dangles<_U1, _U2>() constexpr std::pair<_T1, _T2>::pair(std::pair<_U1, _U2>&&) [with _U2 = _U1; _T1 = int&; _T2 = int]' (deleted)
  354 |         pair(pair<_U1, _U2>&&) = delete;
      |         ^~~~
/usr/include/c++/13/bits/stl_pair.h:354:9: note:   template argument deduction/substitution failed:
/usr/include/c++/13/bits/stl_construct.h:96:17: note:   mismatched types 'std::pair<_T1, _T2>' and 'int*'
   96 |     -> decltype(::new((void*)0) _Tp(std::declval<_Args>()...))
      |                 ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/13/bits/stl_pair.h:345:9: note: candidate: 'template<class _U1, class _U2>  requires  _S_constructible<_U1, _U2>() && !_S_dangles<_U1, _U2>() constexpr std::pair<_T1, _T2>::pair(std::pair<_U1, _U2>&&) [with _U2 = _U1; _T1 = int&; _T2 = int]'
  345 |         pair(pair<_U1, _U2>&& __p)
      |         ^~~~
/usr/include/c++/13/bits/stl_pair.h:345:9: note:   template argument deduction/substitution failed:
/usr/include/c++/13/bits/stl_construct.h:96:17: note:   mismatched types 'std::pair<_T1, _T2>' and 'int*'
   96 |     -> decltype(::new((void*)0) _Tp(std::declval<_Args>()...))
      |                 ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/13/bits/stl_pair.h:339:9: note: candidate: 'template<class _U1, class _U2>  requires  _S_constructible<const _U1&, const _U2&>() && _S_dangles<const _U1&, const _U2&>() constexpr std::pair<_T1, _T2>::pair(const std::pair<_U1, _U2>&) [with _U2 = _U1; _T1 = int&; _T2 = int]' (deleted)
  339 |         pair(const pair<_U1, _U2>&) = delete;
      |         ^~~~
/usr/include/c++/13/bits/stl_pair.h:339:9: note:   template argument deduction/substitution failed:
/usr/include/c++/13/bits/stl_construct.h:96:17: note:   mismatched types 'const std::pair<_T1, _T2>' and 'int*'
   96 |     -> decltype(::new((void*)0) _Tp(std::declval<_Args>()...))
      |                 ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/13/bits/stl_pair.h:330:9: note: candidate: 'template<class _U1, class _U2>  requires  _S_constructible<const _U1&, const _U2&>() && !_S_dangles<_U1, _U2>() constexpr std::pair<_T1, _T2>::pair(const std::pair<_U1, _U2>&) [with _U2 = _U1; _T1 = int&; _T2 = int]'
  330 |         pair(const pair<_U1, _U2>& __p)
      |         ^~~~
/usr/include/c++/13/bits/stl_pair.h:330:9: note:   template argument deduction/substitution failed:
/usr/include/c++/13/bits/stl_construct.h:96:17: note:   mismatched types 'const std::pair<_T1, _T2>' and 'int*'
   96 |     -> decltype(::new((void*)0) _Tp(std::declval<_Args>()...))
      |                 ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/13/bits/stl_pair.h:323:9: note: candidate: 'template<class _U1, class _U2>  requires  _S_constructible<_U1, _U2>() && _S_dangles<_U1, _U2>() constexpr std::pair<_T1, _T2>::pair(_U1&&, _U2&&) [with _U2 = _U1; _T1 = int&; _T2 = int]' (deleted)
  323 |         pair(_U1&&, _U2&&) = delete;
      |         ^~~~
/usr/include/c++/13/bits/stl_pair.h:323:9: note:   template argument deduction/substitution failed:
/usr/include/c++/13/bits/stl_pair.h:323:9: note: constraints not satisfied
/usr/include/c++/13/bits/stl_pair.h: In substitution of 'template<class _U1, class _U2>  requires  _S_constructible<_U1, _U2>() && _S_dangles<_U1, _U2>() constexpr std::pair<int&, int>::pair(_U1&&, _U2&&) [with _U1 = int&; _U2 = int]':
/usr/include/c++/13/bits/stl_construct.h:96:17:   required by substitution of 'template<class _Tp, class ... _Args> constexpr decltype (::new(void*(0)) _Tp) std::construct_at(_Tp*, _Args&& ...) [with _Tp = std::pair<int&, int>; _Args = {int*, int&}]'
/usr/include/c++/13/bits/alloc_traits.h:540:21:   required from 'static constexpr void std::allocator_traits<std::allocator<_CharT> >::construct(allocator_type&, _Up*, _Args&& ...) [with _Up = std::pair<int&, int>; _Args = {int*, int&}; _Tp = std::pair<int&, int>; allocator_type = std::allocator<std::pair<int&, int> >]'
/usr/include/c++/13/bits/vector.tcc:117:30:   required from 'constexpr std::vector<_Tp, _Alloc>::reference std::vector<_Tp, _Alloc>::emplace_back(_Args&& ...) [with _Args = {int*, int&}; _Tp = std::pair<int&, int>; _Alloc = std::allocator<std::pair<int&, int> >; reference = std::pair<int&, int>&]'
collapse.cpp:21:31:   required from here
/usr/include/c++/13/bits/stl_pair.h:323:2:   required by the constraints of 'template<class _T1, class _T2> template<class _U1, class _U2>  requires  _S_constructible<_U1, _U2>() && _S_dangles<_U1, _U2>() constexpr std::pair<_T1, _T2>::pair(_U1&&, _U2&&)'
/usr/include/c++/13/bits/stl_pair.h:321:45: note: the expression '_S_constructible<_U1, _U2>() [with _T1 = int&; _T2 = int; _U1 = int*; _U2 = int&]' evaluated to 'false'
  321 |         requires (_S_constructible<_U1, _U2>()) && (_S_dangles<_U1, _U2>())
      |                  ~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
/usr/include/c++/13/bits/stl_construct.h: In substitution of 'template<class _Tp, class ... _Args> constexpr decltype (::new(void*(0)) _Tp) std::construct_at(_Tp*, _Args&& ...) [with _Tp = std::pair<int&, int>; _Args = {int*, int&}]':
/usr/include/c++/13/bits/alloc_traits.h:540:21:   required from 'static constexpr void std::allocator_traits<std::allocator<_CharT> >::construct(allocator_type&, _Up*, _Args&& ...) [with _Up = std::pair<int&, int>; _Args = {int*, int&}; _Tp = std::pair<int&, int>; allocator_type = std::allocator<std::pair<int&, int> >]'
/usr/include/c++/13/bits/vector.tcc:117:30:   required from 'constexpr std::vector<_Tp, _Alloc>::reference std::vector<_Tp, _Alloc>::emplace_back(_Args&& ...) [with _Args = {int*, int&}; _Tp = std::pair<int&, int>; _Alloc = std::allocator<std::pair<int&, int> >; reference = std::pair<int&, int>&]'
collapse.cpp:21:31:   required from here
/usr/include/c++/13/bits/stl_pair.h:315:9: note: candidate: 'template<class _U1, class _U2>  requires  _S_constructible<_U1, _U2>() && !_S_dangles<_U1, _U2>() constexpr std::pair<_T1, _T2>::pair(_U1&&, _U2&&) [with _U2 = _U1; _T1 = int&; _T2 = int]'
  315 |         pair(_U1&& __x, _U2&& __y)
      |         ^~~~
/usr/include/c++/13/bits/stl_pair.h:315:9: note:   template argument deduction/substitution failed:
/usr/include/c++/13/bits/stl_pair.h:315:9: note: constraints not satisfied
/usr/include/c++/13/bits/stl_pair.h: In substitution of 'template<class _U1, class _U2>  requires  _S_constructible<_U1, _U2>() && !_S_dangles<_U1, _U2>() constexpr std::pair<int&, int>::pair(_U1&&, _U2&&) [with _U1 = int&; _U2 = int]':
/usr/include/c++/13/bits/stl_construct.h:96:17:   required by substitution of 'template<class _Tp, class ... _Args> constexpr decltype (::new(void*(0)) _Tp) std::construct_at(_Tp*, _Args&& ...) [with _Tp = std::pair<int&, int>; _Args = {int*, int&}]'
/usr/include/c++/13/bits/alloc_traits.h:540:21:   required from 'static constexpr void std::allocator_traits<std::allocator<_CharT> >::construct(allocator_type&, _Up*, _Args&& ...) [with _Up = std::pair<int&, int>; _Args = {int*, int&}; _Tp = std::pair<int&, int>; allocator_type = std::allocator<std::pair<int&, int> >]'
/usr/include/c++/13/bits/vector.tcc:117:30:   required from 'constexpr std::vector<_Tp, _Alloc>::reference std::vector<_Tp, _Alloc>::emplace_back(_Args&& ...) [with _Args = {int*, int&}; _Tp = std::pair<int&, int>; _Alloc = std::allocator<std::pair<int&, int> >; reference = std::pair<int&, int>&]'
collapse.cpp:21:31:   required from here
/usr/include/c++/13/bits/stl_pair.h:315:2:   required by the constraints of 'template<class _T1, class _T2> template<class _U1, class _U2>  requires  _S_constructible<_U1, _U2>() && !_S_dangles<_U1, _U2>() constexpr std::pair<_T1, _T2>::pair(_U1&&, _U2&&)'
/usr/include/c++/13/bits/stl_pair.h:313:45: note: the expression '_S_constructible<_U1, _U2>() [with _T1 = int&; _T2 = int; _U1 = int*; _U2 = int&]' evaluated to 'false'
  313 |         requires (_S_constructible<_U1, _U2>()) && (!_S_dangles<_U1, _U2>())
      |                  ~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
/usr/include/c++/13/bits/stl_construct.h: In substitution of 'template<class _Tp, class ... _Args> constexpr decltype (::new(void*(0)) _Tp) std::construct_at(_Tp*, _Args&& ...) [with _Tp = std::pair<int&, int>; _Args = {int*, int&}]':
/usr/include/c++/13/bits/alloc_traits.h:540:21:   required from 'static constexpr void std::allocator_traits<std::allocator<_CharT> >::construct(allocator_type&, _Up*, _Args&& ...) [with _Up = std::pair<int&, int>; _Args = {int*, int&}; _Tp = std::pair<int&, int>; allocator_type = std::allocator<std::pair<int&, int> >]'
/usr/include/c++/13/bits/vector.tcc:117:30:   required from 'constexpr std::vector<_Tp, _Alloc>::reference std::vector<_Tp, _Alloc>::emplace_back(_Args&& ...) [with _Args = {int*, int&}; _Tp = std::pair<int&, int>; _Alloc = std::allocator<std::pair<int&, int> >; reference = std::pair<int&, int>&]'
collapse.cpp:21:31:   required from here
/usr/include/c++/13/bits/stl_pair.h:238:9: note: candidate: 'template<class ... _Args1, long unsigned int ..._Indexes1, class ... _Args2, long unsigned int ..._Indexes2> constexpr std::pair<_T1, _T2>::pair(std::tuple<_Args1 ...>&, std::tuple<_Args2 ...>&, std::_Index_tuple<_Indexes1 ...>, std::_Index_tuple<_Indexes2 ...>) [with _Args1 = {_Args1 ...}; long unsigned int ..._Indexes1 = {_Indexes1 ...}; _Args2 = {_Args2 ...}; long unsigned int ..._Indexes2 = {_Indexes2 ...}; _T1 = int&; _T2 = int]'
  238 |         pair(tuple<_Args1...>&, tuple<_Args2...>&,
      |         ^~~~
/usr/include/c++/13/bits/stl_pair.h:238:9: note:   template argument deduction/substitution failed:
/usr/include/c++/13/bits/stl_construct.h:96:17: note:   mismatched types 'std::tuple<_UTypes ...>' and 'int*'
   96 |     -> decltype(::new((void*)0) _Tp(std::declval<_Args>()...))
      |                 ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/13/bits/stl_pair.h:202:9: note: candidate: 'template<class ... _Args1, class ... _Args2> constexpr std::pair<_T1, _T2>::pair(std::piecewise_construct_t, std::tuple<_Args1 ...>, std::tuple<_Args2 ...>) [with _Args1 = {_Args1 ...}; _Args2 = {_Args2 ...}; _T1 = int&; _T2 = int]'
  202 |         pair(piecewise_construct_t, tuple<_Args1...>, tuple<_Args2...>);
      |         ^~~~
/usr/include/c++/13/bits/stl_pair.h:202:9: note:   template argument deduction/substitution failed:
/usr/include/c++/13/bits/stl_construct.h:96:17: note:   mismatched types 'std::tuple<_UTypes ...>' and 'int'
   96 |     -> decltype(::new((void*)0) _Tp(std::declval<_Args>()...))
      |                 ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/13/bits/stl_pair.h:249:7: note: candidate: 'constexpr std::pair<_T1, _T2>::pair() requires (is_default_constructible_v<_T1>) && (is_default_constructible_v<_T2>) [with _T1 = int&; _T2 = int]'
  249 |       pair()
      |       ^~~~
/usr/include/c++/13/bits/stl_pair.h:249:7: note:   candidate expects 0 arguments, 2 provided
/usr/include/c++/13/bits/stl_pair.h:198:17: note: candidate: 'constexpr std::pair<_T1, _T2>::pair(std::pair<_T1, _T2>&&) [with _T1 = int&; _T2 = int]'
  198 |       constexpr pair(pair&&) = default;         ///< Move constructor
      |                 ^~~~
/usr/include/c++/13/bits/stl_pair.h:198:17: note:   candidate expects 1 argument, 2 provided
/usr/include/c++/13/bits/stl_pair.h:197:17: note: candidate: 'constexpr std::pair<_T1, _T2>::pair(const std::pair<_T1, _T2>&) [with _T1 = int&; _T2 = int]'
  197 |       constexpr pair(const pair&) = default;    ///< Copy constructor
      |                 ^~~~
/usr/include/c++/13/bits/stl_pair.h:197:17: note:   candidate expects 1 argument, 2 provided