Submission #363276

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
363276	2021-02-05T12:23:10 Z	buyolitsez	Collapse (JOI18_collapse)	C++17	Compilation error	0 ms	0 KB

collapse

-#include "collapse.h"
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1e5 + 15;
int p[MAXN];
int rang[MAXN];
vector <int> ans;
int need = -1;
int cntComp;

int GetPar(int v) {
    if (p[v] == -1) {
        return v;
    }
    return GetPar(p[v]);
}

void Comeback(int wasCnt, vector <tuple <int, int, int>> wasDSU) {
    reverse(wasDSU.begin(), wasDSU.end());
    cntComp = wasCnt;
    for (auto [a, b, c] : wasDSU) {
        p[a] = b;
        rang[a] = c;
    }
}

void Func(int l, int r, vector <tuple <int, int, int, int>> edges, vector <pair <int, int>> querys) {
    int m = l + (r - l) / 2;
    vector <tuple <int, int, int, int>> edgesL, edgesR;
    vector <pair <int, int>> querysL, querysR;
    vector <tuple <int, int, int>> wasDSU;
    int wasCnt = cntComp;
    for (auto [a, b, x, y] : edges) {
        if (min(a, b) <= need && max(a, b) >= need + 1) {continue;}
        if (x <= l && r <= y) {
            a = GetPar(a);
            b = GetPar(b);
            if (a == b) {continue;}
            wasDSU.emplace_back(a, p[a], rang[a]);
            wasDSU.emplace_back(b, p[b], rang[b]);
            if (rang[a] > rang[b]) {swap(a, b);}
            --cntComp;
            rang[b] += rang[a];
            p[a] = b;
        } else {
            if (!(y < l || x > m)) {
                edgesL.emplace_back(a, b, x, y);
            }
            if (!(m + 1 > y || r < x)) {
                edgesR.emplace_back(a, b, x, y);
            }
        }
    }
    if (l == r) {
        for (auto [pos, num] : querys) {
            ans[num] = cntComp;
        }
        Comeback(wasCnt, wasDSU);
        return;
    }
    for (auto [pos, num] : querys) {
        if (pos <= m) {
            querysL.emplace_back(pos, num);
        } else {
            querysR.emplace_back(pos, num);
        }
    }
    Func(l, m, edgesL, querysL);
    Func(m + 1, r, edgesR, querysR);
    Comeback(wasCnt, wasDSU);
}

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) {
    memset(p, -1, sizeof(p));
    fill(rang, rang + MAXN, 1);
    cntComp = N;
    vector <tuple <int, int, int, int>> edges;
    map <pair <int, int>, int> last;
    ans.resize(W.size(), -1);
    for (int i = 0; i < T.size(); ++i) {
        int type = T[i], a = X[i], b = Y[i];
        if (type == 0) {
            last[{min(a, b), max(a, b)}] = i;
        } else {
            edges.emplace_back(a, b, last[{min(a, b), max(a, b)}], i - 1);
            last.erase(last.find({min(a, b), max(a, b)}));
        }
    }
    for (auto [x, y] : last) {
        edges.emplace_back(x.first, x.second, y, T.size() - 1);
    }
    vector <pair <int, int>> querys(W.size());
    for (int i = 0; i < W.size(); ++i) {
        int w = W[i], p = P[i];
        if (need == -1) {
            need = p;
        }
        assert(need == p);
        querys[i] = {w, i};
    }
    Func(0, T.size() - 1, edges, querys);
    return ans;
}

Compilation message

collapse.cpp:1:2: error: stray '#' in program
    1 | -#include "collapse.h"
      |  ^
collapse.cpp:1:1: error: expected unqualified-id before '-' token
    1 | -#include "collapse.h"
      | ^
In file included from /usr/include/c++/9/cmath:43,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:41,
                 from collapse.cpp:2:
/usr/include/c++/9/ext/type_traits.h:162:35: error: 'bool __gnu_cxx::__is_null_pointer' redeclared as different kind of entity
  162 |   __is_null_pointer(std::nullptr_t)
      |                                   ^
/usr/include/c++/9/ext/type_traits.h:157:5: note: previous declaration 'template<class _Type> bool __gnu_cxx::__is_null_pointer(_Type)'
  157 |     __is_null_pointer(_Type)
      |     ^~~~~~~~~~~~~~~~~
/usr/include/c++/9/ext/type_traits.h:162:26: error: 'nullptr_t' is not a member of 'std'
  162 |   __is_null_pointer(std::nullptr_t)
      |                          ^~~~~~~~~
In file included from /usr/include/c++/9/bits/move.h:55,
                 from /usr/include/c++/9/bits/stl_pair.h:59,
                 from /usr/include/c++/9/bits/stl_algobase.h:64,
                 from /usr/include/c++/9/bits/specfun.h:45,
                 from /usr/include/c++/9/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:41,
                 from collapse.cpp:2:
/usr/include/c++/9/type_traits:361:26: error: 'std::size_t' has not been declared
  361 |   template<typename _Tp, std::size_t _Size>
      |                          ^~~
/usr/include/c++/9/type_traits:362:25: error: '_Size' was not declared in this scope
  362 |     struct is_array<_Tp[_Size]>
      |                         ^~~~~
/usr/include/c++/9/type_traits:362:31: error: template argument 1 is invalid
  362 |     struct is_array<_Tp[_Size]>
      |                               ^
/usr/include/c++/9/type_traits:560:42: error: 'nullptr_t' is not a member of 'std'
  560 |     struct __is_null_pointer_helper<std::nullptr_t>
      |                                          ^~~~~~~~~
/usr/include/c++/9/type_traits:560:51: error: template argument 1 is invalid
  560 |     struct __is_null_pointer_helper<std::nullptr_t>
      |                                                   ^
/usr/include/c++/9/type_traits:1253:37: error: 'size_t' is not a member of 'std'; did you mean 'size_t'?
 1253 |     : public integral_constant<std::size_t, alignof(_Tp)> { };
      |                                     ^~~~~~
In file included from /usr/include/stdlib.h:31,
                 from /usr/include/c++/9/bits/std_abs.h:38,
                 from /usr/include/c++/9/cmath:47,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:41,
                 from collapse.cpp:2:
/usr/lib/gcc/x86_64-linux-gnu/9/include/stddef.h:209:23: note: 'size_t' declared here
  209 | typedef __SIZE_TYPE__ size_t;
      |                       ^~~~~~
In file included from /usr/include/c++/9/bits/move.h:55,
                 from /usr/include/c++/9/bits/stl_pair.h:59,
                 from /usr/include/c++/9/bits/stl_algobase.h:64,
                 from /usr/include/c++/9/bits/specfun.h:45,
                 from /usr/include/c++/9/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:41,
                 from collapse.cpp:2:
/usr/include/c++/9/type_traits:1253:57: error: template argument 1 is invalid
 1253 |     : public integral_constant<std::size_t, alignof(_Tp)> { };
      |                                                         ^
/usr/include/c++/9/type_traits:1253:57: note: invalid template non-type parameter
/usr/include/c++/9/type_traits:1258:37: error: 'size_t' is not a member of 'std'; did you mean 'size_t'?
 1258 |     : public integral_constant<std::size_t, 0> { };
      |                                     ^~~~~~
In file included from /usr/include/stdlib.h:31,
                 from /usr/include/c++/9/bits/std_abs.h:38,
                 from /usr/include/c++/9/cmath:47,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:41,
                 from collapse.cpp:2:
/usr/lib/gcc/x86_64-linux-gnu/9/include/stddef.h:209:23: note: 'size_t' declared here
  209 | typedef __SIZE_TYPE__ size_t;
      |                       ^~~~~~
In file included from /usr/include/c++/9/bits/move.h:55,
                 from /usr/include/c++/9/bits/stl_pair.h:59,
                 from /usr/include/c++/9/bits/stl_algobase.h:64,
                 from /usr/include/c++/9/bits/specfun.h:45,
                 from /usr/include/c++/9/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:41,
                 from collapse.cpp:2:
/usr/include/c++/9/type_traits:1258:46: error: template argument 1 is invalid
 1258 |     : public integral_constant<std::size_t, 0> { };
      |                                              ^
/usr/include/c++/9/type_traits:1258:46: note: invalid template non-type parameter
/usr/include/c++/9/type_traits:1260:26: error: 'std::size_t' has not been declared
 1260 |   template<typename _Tp, std::size_t _Size>
      |                          ^~~
/usr/include/c++/9/type_traits:1261:21: error: '_Size' was not declared in this scope
 1261 |     struct rank<_Tp[_Size]>
      |                     ^~~~~
/usr/include/c++/9/type_traits:1261:27: error: template argument 1 is invalid
 1261 |     struct rank<_Tp[_Size]>
      |                           ^
/usr/include/c++/9/type_traits:1262:37: error: 'size_t' is not a member of 'std'; did you mean 'size_t'?
 1262 |     : public integral_constant<std::size_t, 1 + rank<_Tp>::value> { };
      |                                     ^~~~~~
In file included from /usr/include/stdlib.h:31,
                 from /usr/include/c++/9/bits/std_abs.h:38,
                 from /usr/include/c++/9/cmath:47,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:41,
                 from collapse.cpp:2:
/usr/lib/gcc/x86_64-linux-gnu/9/include/stddef.h:209:23: note: 'size_t' declared here
  209 | typedef __SIZE_TYPE__ size_t;
      |                       ^~~~~~
In file included from /usr/include/c++/9/bits/move.h:55,
                 from /usr/include/c++/9/bits/stl_pair.h:59,
                 from /usr/include/c++/9/bits/stl_algobase.h:64,
                 from /usr/include/c++/9/bits/specfun.h:45,
                 from /usr/include/c++/9/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:41,
                 from collapse.cpp:2:
/usr/include/c++/9/type_traits:1262:65: error: template argument 1 is invalid
 1262 |     : public integral_constant<std::size_t, 1 + rank<_Tp>::value> { };
      |                                                                 ^
/usr/include/c++/9/type_traits:1262:65: note: invalid template non-type parameter
/usr/include/c++/9/type_traits:1266:37: error: 'size_t' is not a member of 'std'; did you mean 'size_t'?
 1266 |     : public integral_constant<std::size_t, 1 + rank<_Tp>::value> { };
      |                                     ^~~~~~
In file included from /usr/include/stdlib.h:31,
                 from /usr/include/c++/9/bits/std_abs.h:38,
                 from /usr/include/c++/9/cmath:47,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:41,
                 from collapse.cpp:2:
/usr/lib/gcc/x86_64-linux-gnu/9/include/stddef.h:209:23: note: 'size_t' declared here
  209 | typedef __SIZE_TYPE__ size_t;
      |                       ^~~~~~
In file included from /usr/include/c++/9/bits/move.h:55,
                 from /usr/include/c++/9/bits/stl_pair.h:59,
                 from /usr/include/c++/9/bits/stl_algobase.h:64,
                 from /usr/include/c++/9/bits/specfun.h:45,
                 from /usr/include/c++/9/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:41,
                 from collapse.cpp:2:
/usr/include/c++/9/type_traits:1266:65: error: template argument 1 is invalid
 1266 |     : public integral_constant<std::size_t, 1 + rank<_Tp>::value> { };
      |                                                                 ^
/usr/include/c++/9/type_traits:1266:65: note: invalid template non-type parameter
/usr/include/c++/9/type_traits:1271:37: error: 'size_t' is not a member of 'std'; did you mean 'size_t'?
 1271 |     : public integral_constant<std::size_t, 0> { };
      |                                     ^~~~~~
In file included from /usr/include/stdlib.h:31,
                 from /usr/include/c++/9/bits/std_abs.h:38,
                 from /usr/include/c++/9/cmath:47,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:41,
                 from collapse.cpp:2:
/usr/lib/gcc/x86_64-linux-gnu/9/include/stddef.h:209:23: note: 'size_t' declared here
  209 | typedef __SIZE_TYPE__ size_t;
      |                       ^~~~~~
In file included from /usr/include/c++/9/bits/move.h:55,
                 from /usr/include/c++/9/bits/stl_pair.h:59,
                 from /usr/include/c++/9/bits/stl_algobase.h:64,
                 from /usr/include/c++/9/bits/specfun.h:45,
                 from /usr/include/c++/9/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:41,
                 from collapse.cpp:2:
/usr/include/c++/9/type_traits:1271:46: error: template argument 1 is invalid
 1271 |     : public integral_constant<std::size_t, 0> { };
      |                                              ^
/usr/include/c++/9/type_traits:1271:46: note: invalid template non-type parameter
/usr/include/c++/9/type_traits:1273:42: error: 'std::size_t' has not been declared
 1273 |   template<typename _Tp, unsigned _Uint, std::size_t _Size>
      |                                          ^~~
/usr/include/c++/9/type_traits:1274:23: error: '_Size' was not declared in this scope
 1274 |     struct extent<_Tp[_Size], _Uint>
      |                       ^~~~~
/usr/include/c++/9/type_traits:1274:36: error: template argument 1 is invalid
 1274 |     struct extent<_Tp[_Size], _Uint>
      |                                    ^
/usr/include/c++/9/type_traits:1275:37: error: 'size_t' is not a member of 'std'; did you mean 'size_t'?
 1275 |     : public integral_constant<std::size_t,
      |                                     ^~~~~~
In file included from /usr/include/stdlib.h:31,
                 from /usr/include/c++/9/bits/std_abs.h:38,
                 from /usr/include/c++/9/cmath:47,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:41,
                 from collapse.cpp:2:
/usr/lib/gcc/x86_64-linux-gnu/9/include/stddef.h:209:23: note: 'size_t' declared here
  209 | typedef __SIZE_TYPE__ size_t;
      |                       ^~~~~~
In file included from /usr/include/c++/9/bits/move.h:55,
                 from /usr/include/c++/9/bits/stl_pair.h:59,
                 from /usr/include/c++/9/bits/stl_algobase.h:64,
                 from /usr/include/c++/9/bits/specfun.h:45,
                 from /usr/include/c++/9/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:41,
                 from collapse.cpp:2:
/usr/include/c++/9/type_traits:1276:24: error: '_Size' was not declared in this scope
 1276 |           _Uint == 0 ? _Size : extent<_Tp,
      |                        ^~~~~
/usr/include/c++/9/type_traits:1277:28: error: template argument 1 is invalid
 1277 |           _Uint - 1>::value>
      |                            ^
/usr/include/c++/9/type_traits:1277:28: note: invalid template non-type parameter
/usr/include/c++/9/type_traits:1282:37: error: 'size_t' is not a member of 'std'; did you mean 'size_t'?
 1282 |     : public integral_constant<std::size_t,
      |                                     ^~~~~~
In file included from /usr/include/stdlib.h:31,
                 from /usr/include/c++/9/bits/std_abs.h:38,
                 from /usr/include/c++/9/cmath:47,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:41,
                 from collapse.cpp:2:
/usr/lib/gcc/x86_64-linux-gnu/9/include/stddef.h:209:23: note: 'size_t' declared here
  209 | typedef __SIZE_TYPE__ size_t;
      |                       ^~~~~~
In file included from /usr/include/c++/9/bits/move.h:55,
                 from /usr/include/c++/9/bits/stl_pair.h:59,
                 from /usr/include/c++/9/bits/stl_algobase.h:64,
                 from /usr/include/c++/9/bits/specfun.h:45,
                 from /usr/include/c++/9/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:41,
                 from collapse.cpp:2:
/usr/include/c++/9/type_traits:1284:31: error: template argument 1 is invalid
 1284 |              _Uint - 1>::value>
      |                               ^
/usr/include/c++/9/type_traits:1284:31: note: invalid template non-type parameter
/usr/include/c++/9/type_traits:1838:26: error: 'std::size_t' has not been declared
 1838 |   template<typename _Tp, std::size_t _Size>
      |                          ^~~
/usr/include/c++/9/type_traits:1839:30: error: '_Size' was not declared in this scope
 1839 |     struct remove_extent<_Tp[_Size]>
      |                              ^~~~~
/usr/include/c++/9/type_traits:1839:36: error: template argument 1 is invalid
 1839 |     struct remove_extent<_Tp[_Size]>
      |                                    ^
/usr/include/c++/9/type_traits:1851:26: error: 'std::size_t' has not been declared
 1851 |   template<typename _Tp, std::size_t _Size>
      |                          ^~~
/usr/include/c++/9/type_traits:1852:35: error: '_Size' was not declared in this scope
 1852 |     struct remove_all_extents<_Tp[_Size]>
      |                                   ^~~~~
/usr/include/c++/9/type_traits:1852:41: error: template argument 1 is invalid
 1852 |     struct remove_all_extents<_Tp[_Size]>
      |                                         ^
/usr/include/c++/9/type_traits:1910:12: error: 'std::size_t' has not been declared
 1910 |   template<std::size_t _Len>
      |            ^~~
/usr/include/c++/9/type_traits:1915:23: error: '_Len' was not declared in this scope
 1915 |  unsigned char __data[_Len];
      |                       ^~~~
/usr/include/c++/9/type_traits:1930:12: error: 'std::size_t' has not been declared
 1930 |   template<std::size_t _Len, std::size_t _Align =
      |            ^~~
/usr/include/c++/9/type_traits:1930:30: error: 'std::size_t' has not been declared
 1930 |   template<std::size_t _Len, std::size_t _Align =
      |                              ^~~
/usr/include/c++/9/type_traits:1931:48: error: '_Len' was not declared in this scope
 1931 |     __alignof__(typename __aligned_storage_msa<_Len>::__type)>
      |                                                ^~~~
/usr/include/c++/9/type_traits:1931:52: error: template argument 1 is invalid
 1931 |     __alignof__(typename __aligned_storage_msa<_Len>::__type)>
      |                                                    ^
/usr/include/c++/9/type_traits:1936:23: error: '_Len' was not declared in this scope
 1936 |  unsigned char __data[_Len];
      |                       ^~~~
/usr/include/c++/9/type_traits:1937:37: error: '_Align' was not declared in this scope
 1937 |  struct __attribute__((__aligned__((_Align)))) { } __align;
      |                                     ^~~~~~
In file included from /usr/include/c++/9/bits/stl_algobase.h:64,
                 from /usr/include/c++/9/bits/specfun.h:45,
                 from /usr/include/c++/9/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:41,
                 from collapse.cpp:2:
/usr/include/c++/9/bits/stl_pair.h:86:12: error: 'std::size_t' has not been declared
   86 |   template<std::size_t...>
      |            ^~~
/usr/include/c++/9/bits/stl_pair.h:434:36: error: 'std::size_t' has not been declared
  434 |       template<typename... _Args1, std::size_t... _Indexes1,
      |                                    ^~~
/usr/include/c++/9/bits/stl_pair.h:435:36: error: 'std::size_t' has not been declared
  435 |                typename... _Args2, std::size_t... _Indexes2>
      |                                    ^~~
/usr/include/c++/9/bits/stl_pair.h:437:27: error: '_Indexes1' was not declared in this scope
  437 |              _Index_tuple<_Indexes1...>, _Index_tuple<_Indexes2...>);
      |                           ^~~~~~~~~
/usr/include/c++/9/bits/stl_pair.h:437:36: error: expected parameter pack before '...'
  437 |              _Index_tuple<_Indexes1...>, _Index_tuple<_Indexes2...>);
      |                                    ^~~
/usr/include/c++/9/bits/stl_pair.h:437:39: error: template argument 1 is invalid
  437 |              _Index_tuple<_Indexes1...>, _Index_tuple<_Indexes2...>);
      |                                       ^
/usr/include/c++/9/bits/stl_pair.h:437:55: error: '_Indexes2' was not declared in this scope
  437 |              _Index_tuple<_Indexes1...>, _Index_tuple<_Indexes2...>);
      |                                                       ^~~~~~~~~
/usr/include/c++/9/bits/stl_pair.h:437:64: error: expected parameter pack before '...'
  437 |              _Index_tuple<_Indexes1...>, _Index_tuple<_Indexes2...>);
      |                                                                ^~~
/usr/include/c++/9/bits/stl_pair.h:437:67: error: template argument 1 is invalid
  437 |              _Index_tuple<_Indexes1...>, _Index_tuple<_Indexes2...>);
      |                                                                   ^
In file included from /usr/include/c++/9/bits/stl_algobase.h:65,
                 from /usr/include/c++/9/bits/specfun.h:45,
                 from /usr/include/c++/9/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:41,
                 from collapse.cpp:2:
/usr/include/c++/9/bits/stl_iterator_base_types.h:116:67: error: 'ptrdiff_t' does not name a type
  116 |   template<typename _Category, typename _Tp, typename _Distance = ptrdiff_t,
      |                                                                   ^~~~~~~~~
In file included from /usr/include/c++/9/bits/stl_algobase.h:65,
                 from /usr/include/c++/9/bits/specfun.h:45,
                 from /usr/include/c++/9/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:41,
                 from collapse.cpp:2:
/usr/include/c++/9/bits/stl_iterator_base_types.h:1:1: note: 'ptrdiff_t' is defined in header '<cstddef>'; did you forget to '#include <cstddef>'?
  +++ |+#include <cstddef>
    1 | // Types used in iterator implementation -*- C++ -*-
In file included from /usr/include/c++/9/bits/stl_algobase.h:65,
                 from /usr/include/c++/9/bits/specfun.h:45,
                 from /usr/include/c++/9/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:41,
                 from collapse.cpp:2:
/usr/include/c++/9/bits/stl_iterator_base_types.h:182:15: error: 'ptrdiff_t' does not name a type
  182 |       typedef ptrdiff_t                   difference_type;
      |               ^~~~~~~~~
/usr/include/c++/9/bits/stl_iterator_base_types.h:182:15: note: 'ptrdiff_t' is defined in header '<cstddef>'; did you forget to '#include <cstddef>'?
/usr/include/c++/9/bits/stl_iterator_base_types.h:193:15: error: 'ptrdiff_t' does not name a type
  193 |       typedef ptrdiff_t