Submission #424991

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
424991	2021-06-12T12:15:58 Z	CodePlatina	Collapse (JOI18_collapse)	C++17	Compilation error	0 ms	0 KB

collapse

#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <tuple>
#include <map>
#include <set>
#include <cstdlib>
#include <unordered_set>
#define pii pair<int, int>
#define piii pair<int, pii>
#define pll pair<long long, long long>
#define plll pair<long long, pll>
#define tiii tuple<int, int, int>
#define tiiii tuple<int, int, int, int>
#define ff first
#define ss second
#define ee ss.ff
#define rr ss.ss
#define DEBUG
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")
const int INF = (int)1e9 + 7;
const int Q = 320;

using namespace std;

vector<pii> eg;
vector<pii> lf;
map<pii, int> M;
vector<int> lsu[101010];
vector<int> lsd[101010];
vector<pii> qr[101010];

struct UF
{
    int par[101010];
    short rnk[101010];
    int pnt;
    int cnt, __cnt;
    vector<pii> rec;

    UF(void) : pnt(0), cnt(0), __cnt(0), rec() { for(int i = 0; i < 101010; ++i) par[i] = i, rnk[i] = 0; }
    int fnd(int x) { return x == par[x] ? x : fnd(par[x]); }
    void uni(int x, int y)
    {
        x = fnd(x), y = fnd(y);
        if(x == y) return;
        if(rnk[x] == rnk[y])
        {
            rec.push_back({0, x});
            rec.push_back({1, y});
            ++rnk[x];
            par[y] = x;
        }
        else if(rnk[x] > rnk[y])
        {
            rec.push_back({1, y});
            par[y] = x;
        }
        else
        {
            rec.push_back({1, x});
            par[x] = y;
        }
        ++cnt;
    }
    void save(void) { pnt = (int)rec.size(); __cnt = cnt; }
    void rollback(void)
    {
        while((int)rec.size() > pnt)
        {
            auto [c, x] = rec.back();
            if(c == 0) --rnk[x];
            else par[x] = x;
            rec.pop_back();
        }
        cnt = __cnt;
    }
}uf[320];

vector<int> ind[320];

vector<int> simulateCollapse(int N, vecotr<int> C, vector<int> X, vecotr<int> Y, vector<int> W, vector<int>P)
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n = N, m = C.size(), T = W.size();
    for(int i = 0; i < m; ++i)
    {
        int c = C[i], x = X[i], y = Y[i];
        if(x > y) swap(x, y);

        if(c == 0)
        {
            M[{x, y}] = (int)eg.size();
            eg.push_back({x, y});
            lf.push_back({i, m});
        }
        else
        {
            lf[M[{x, y}]].ss = i;
            M.erase({x, y});
        }
    }
    for(int i = 0; i < (int)eg.size(); ++i)
    {
        if(eg[i].ff > 0) lsd[eg[i].ff - 1].push_back(i);
        lsu[eg[i].ss].push_back(i);
    }

    for(int i = 0; i < T; ++i)
    {
        int x = W[i], y = P[i];
        qr[y].push_back({x, i});
    }

    vector<int> ans(T); for(auto &i : ans) i = n;
    for(int i = 0; i < n; ++i)
    {
        for(int k = 0; k < (int)lsu[i].size(); ++k)
        {
            auto [x, y] = eg[lsu[i][k]];
            auto [s, e] = lf[lsu[i][k]];
            for(int j = s / Q; j <= (e - 1) / Q; ++j)
            {
                int l = j * Q, r = l + Q;
                if(s <= l && r <= e) uf[j].uni(x, y);
                else ind[j].push_back(lsu[i][k]);
            }
        }

        for(auto [t, q] : qr[i])
        {
            int j = t / Q;
            uf[j].save();
            for(int k = 0; k < (int)ind[j].size(); ++k)
            {
                auto [x, y] = eg[ind[j][k]];
                auto [s, e] = lf[ind[j][k]];
                if(s <= t && t < e) uf[j].uni(x, y);
            }
            ans[q] -= uf[j].cnt;
            uf[j].rollback();
        }
    }

    for(int i = 0; i < 320; ++i)
    {
        uf[i].pnt = uf[i].cnt = uf[i].__cnt = 0;
        uf[i].rollback();
        ind[i].clear();
        ind[i].shrink_to_fit();
    }

    for(int i = n - 1; i >= 0; --i)
    {
        for(int k = 0; k < (int)lsd[i].size(); ++k)
        {
            auto [x, y] = eg[lsd[i][k]];
            auto [s, e] = lf[lsd[i][k]];
            for(int j = s / Q; j <= (e - 1) / Q; ++j)
            {
                int l = j * Q, r = l + Q;
                if(s <= l && r <= e) uf[j].uni(x, y);
                else ind[j].push_back(lsd[i][k]);
            }
        }

        for(auto [t, q] : qr[i])
        {
            int j = t / Q;
            uf[j].save();
            for(int k = 0; k < (int)ind[j].size(); ++k)
            {
                auto [x, y] = eg[ind[j][k]];
                auto [s, e] = lf[ind[j][k]];
                if(s <= t && t < e) uf[j].uni(x, y);
            }
            ans[q] -= uf[j].cnt;
            uf[j].rollback();
        }
    }

	return ans;
}

Compilation message

collapse.cpp:85:37: error: 'vecotr' has not been declared
   85 | vector<int> simulateCollapse(int N, vecotr<int> C, vector<int> X, vecotr<int> Y, vector<int> W, vector<int>P)
      |                                     ^~~~~~
collapse.cpp:85:43: error: expected ',' or '...' before '<' token
   85 | vector<int> simulateCollapse(int N, vecotr<int> C, vector<int> X, vecotr<int> Y, vector<int> W, vector<int>P)
      |                                           ^
collapse.cpp: In function 'std::vector<int> simulateCollapse(int, int)':
collapse.cpp:90:20: error: 'C' was not declared in this scope
   90 |     int n = N, m = C.size(), T = W.size();
      |                    ^
collapse.cpp:94:12: error: 'x' was not declared in this scope
   94 |         if(x > y) swap(x, y);
      |            ^
collapse.cpp:94:16: error: 'y' was not declared in this scope
   94 |         if(x > y) swap(x, y);
      |                ^
collapse.cpp:98:16: error: 'x' was not declared in this scope
   98 |             M[{x, y}] = (int)eg.size();
      |                ^
collapse.cpp:98:19: error: 'y' was not declared in this scope
   98 |             M[{x, y}] = (int)eg.size();
      |                   ^
collapse.cpp:98:14: error: no match for 'operator[]' (operand types are 'std::map<std::pair<int, int>, int>' and '<brace-enclosed initializer list>')
   98 |             M[{x, y}] = (int)eg.size();
      |              ^
In file included from /usr/include/c++/10/map:61,
                 from collapse.cpp:6:
/usr/include/c++/10/bits/stl_map.h:492:7: note: candidate: 'std::map<_Key, _Tp, _Compare, _Alloc>::mapped_type& std::map<_Key, _Tp, _Compare, _Alloc>::operator[](const key_type&) [with _Key = std::pair<int, int>; _Tp = int; _Compare = std::less<std::pair<int, int> >; _Alloc = std::allocator<std::pair<const std::pair<int, int>, int> >; std::map<_Key, _Tp, _Compare, _Alloc>::mapped_type = int; std::map<_Key, _Tp, _Compare, _Alloc>::key_type = std::pair<int, int>]'
  492 |       operator[](const key_type& __k)
      |       ^~~~~~~~
/usr/include/c++/10/bits/stl_map.h:492:34: note:   no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'const key_type&' {aka 'const std::pair<int, int>&'}
  492 |       operator[](const key_type& __k)
      |                  ~~~~~~~~~~~~~~~~^~~
/usr/include/c++/10/bits/stl_map.h:512:7: note: candidate: 'std::map<_Key, _Tp, _Compare, _Alloc>::mapped_type& std::map<_Key, _Tp, _Compare, _Alloc>::operator[](std::map<_Key, _Tp, _Compare, _Alloc>::key_type&&) [with _Key = std::pair<int, int>; _Tp = int; _Compare = std::less<std::pair<int, int> >; _Alloc = std::allocator<std::pair<const std::pair<int, int>, int> >; std::map<_Key, _Tp, _Compare, _Alloc>::mapped_type = int; std::map<_Key, _Tp, _Compare, _Alloc>::key_type = std::pair<int, int>]'
  512 |       operator[](key_type&& __k)
      |       ^~~~~~~~
/usr/include/c++/10/bits/stl_map.h:512:29: note:   no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'std::map<std::pair<int, int>, int>::key_type&&' {aka 'std::pair<int, int>&&'}
  512 |       operator[](key_type&& __k)
      |                  ~~~~~~~~~~~^~~
collapse.cpp:99:32: error: no matching function for call to 'std::vector<std::pair<int, int> >::push_back(<brace-enclosed initializer list>)'
   99 |             eg.push_back({x, y});
      |                                ^
In file included from /usr/include/c++/10/vector:67,
                 from collapse.cpp:2:
/usr/include/c++/10/bits/stl_vector.h:1187:7: note: candidate: 'void std::vector<_Tp, _Alloc>::push_back(const value_type&) [with _Tp = std::pair<int, int>; _Alloc = std::allocator<std::pair<int, int> >; std::vector<_Tp, _Alloc>::value_type = std::pair<int, int>]'
 1187 |       push_back(const value_type& __x)
      |       ^~~~~~~~~
/usr/include/c++/10/bits/stl_vector.h:1187:35: note:   no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'const value_type&' {aka 'const std::pair<int, int>&'}
 1187 |       push_back(const value_type& __x)
      |                 ~~~~~~~~~~~~~~~~~~^~~
/usr/include/c++/10/bits/stl_vector.h:1203:7: note: candidate: 'void std::vector<_Tp, _Alloc>::push_back(std::vector<_Tp, _Alloc>::value_type&&) [with _Tp = std::pair<int, int>; _Alloc = std::allocator<std::pair<int, int> >; std::vector<_Tp, _Alloc>::value_type = std::pair<int, int>]'
 1203 |       push_back(value_type&& __x)
      |       ^~~~~~~~~
/usr/include/c++/10/bits/stl_vector.h:1203:30: note:   no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'std::vector<std::pair<int, int> >::value_type&&' {aka 'std::pair<int, int>&&'}
 1203 |       push_back(value_type&& __x)
      |                 ~~~~~~~~~~~~~^~~
collapse.cpp:104:19: error: 'x' was not declared in this scope
  104 |             lf[M[{x, y}]].ss = i;
      |                   ^
collapse.cpp:104:22: error: 'y' was not declared in this scope
  104 |             lf[M[{x, y}]].ss = i;
      |                      ^
collapse.cpp:104:17: error: no match for 'operator[]' (operand types are 'std::map<std::pair<int, int>, int>' and '<brace-enclosed initializer list>')
  104 |             lf[M[{x, y}]].ss = i;
      |                 ^
In file included from /usr/include/c++/10/map:61,
                 from collapse.cpp:6:
/usr/include/c++/10/bits/stl_map.h:492:7: note: candidate: 'std::map<_Key, _Tp, _Compare, _Alloc>::mapped_type& std::map<_Key, _Tp, _Compare, _Alloc>::operator[](const key_type&) [with _Key = std::pair<int, int>; _Tp = int; _Compare = std::less<std::pair<int, int> >; _Alloc = std::allocator<std::pair<const std::pair<int, int>, int> >; std::map<_Key, _Tp, _Compare, _Alloc>::mapped_type = int; std::map<_Key, _Tp, _Compare, _Alloc>::key_type = std::pair<int, int>]'
  492 |       operator[](const key_type& __k)
      |       ^~~~~~~~
/usr/include/c++/10/bits/stl_map.h:492:34: note:   no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'const key_type&' {aka 'const std::pair<int, int>&'}
  492 |       operator[](const key_type& __k)
      |                  ~~~~~~~~~~~~~~~~^~~
/usr/include/c++/10/bits/stl_map.h:512:7: note: candidate: 'std::map<_Key, _Tp, _Compare, _Alloc>::mapped_type& std::map<_Key, _Tp, _Compare, _Alloc>::operator[](std::map<_Key, _Tp, _Compare, _Alloc>::key_type&&) [with _Key = std::pair<int, int>; _Tp = int; _Compare = std::less<std::pair<int, int> >; _Alloc = std::allocator<std::pair<const std::pair<int, int>, int> >; std::map<_Key, _Tp, _Compare, _Alloc>::mapped_type = int; std::map<_Key, _Tp, _Compare, _Alloc>::key_type = std::pair<int, int>]'
  512 |       operator[](key_type&& __k)
      |       ^~~~~~~~
/usr/include/c++/10/bits/stl_map.h:512:29: note:   no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'std::map<std::pair<int, int>, int>::key_type&&' {aka 'std::pair<int, int>&&'}
  512 |       operator[](key_type&& __k)
      |                  ~~~~~~~~~~~^~~
collapse.cpp:105:27: error: no matching function for call to 'std::map<std::pair<int, int>, int>::erase(<brace-enclosed initializer list>)'
  105 |             M.erase({x, y});
      |                           ^
In file included from /usr/include/c++/10/map:61,
                 from collapse.cpp:6:
/usr/include/c++/10/bits/stl_map.h:1031:7: note: candidate: 'std::map<_Key, _Tp, _Compare, _Alloc>::iterator std::map<_Key, _Tp, _Compare, _Alloc>::erase(std::map<_Key, _Tp, _Compare, _Alloc>::const_iterator) [with _Key = std::pair<int, int>; _Tp = int; _Compare = std::less<std::pair<int, int> >; _Alloc = std::allocator<std::pair<const std::pair<int, int>, int> >; std::map<_Key, _Tp, _Compare, _Alloc>::iterator = std::_Rb_tree<std::pair<int, int>, std::pair<const std::pair<int, int>, int>, std::_Select1st<std::pair<const std::pair<int, int>, int> >, std::less<std::pair<int, int> >, std::allocator<std::pair<const std::pair<int, int>, int> > >::iterator; std::map<_Key, _Tp, _Compare, _Alloc>::const_iterator = std::_Rb_tree<std::pair<int, int>, std::pair<const std::pair<int, int>, int>, std::_Select1st<std::pair<const std::pair<int, int>, int> >, std::less<std::pair<int, int> >, std::allocator<std::pair<const std::pair<int, int>, int> > >::const_iterator]'
 1031 |       erase(const_iterator __position)
      |       ^~~~~
/usr/include/c++/10/bits/stl_map.h:1031:28: note:   no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'std::map<std::pair<int, int>, int>::const_iterator' {aka 'std::_Rb_tree<std::pair<int, int>, std::pair<const std::pair<int, int>, int>, std::_Select1st<std::pair<const std::pair<int, int>, int> >, std::less<std::pair<int, int> >, std::allocator<std::pair<const std::pair<int, int>, int> > >::const_iterator'}
 1031 |       erase(const_iterator __position)
      |             ~~~~~~~~~~~~~~~^~~~~~~~~~
/usr/include/c++/10/bits/stl_map.h:1037:7: note: candidate: 'std::map<_Key, _Tp, _Compare, _Alloc>::iterator std::map<_Key, _Tp, _Compare, _Alloc>::erase(std::map<_Key, _Tp, _Compare, _Alloc>::iterator) [with _Key = std::pair<int, int>; _Tp = int; _Compare = std::less<std::pair<int, int> >; _Alloc = std::allocator<std::pair<const std::pair<int, int>, int> >; std::map<_Key, _Tp, _Compare, _Alloc>::iterator = std::_Rb_tree<std::pair<int, int>, std::pair<const std::pair<int, int>, int>, std::_Select1st<std::pair<const std::pair<int, int>, int> >, std::less<std::pair<int, int> >, std::allocator<std::pair<const std::pair<int, int>, int> > >::iterator]'
 1037 |       erase(iterator __position)
      |       ^~~~~
/usr/include/c++/10/bits/stl_map.h:1037:22: note:   no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'std::map<std::pair<int, int>, int>::iterator' {aka 'std::_Rb_tree<std::pair<int, int>, std::pair<const std::pair<int, int>, int>, std::_Select1st<std::pair<const std::pair<int, int>, int> >, std::less<std::pair<int, int> >, std::allocator<std::pair<const std::pair<int, int>, int> > >::iterator'}
 1037 |       erase(iterator __position)
      |             ~~~~~~~~~^~~~~~~~~~
/usr/include/c++/10/bits/stl_map.h:1068:7: note: candidate: 'std::map<_Key, _Tp, _Compare, _Alloc>::size_type std::map<_Key, _Tp, _Compare, _Alloc>::erase(const key_type&) [with _Key = std::pair<int, int>; _Tp = int; _Compare = std::less<std::pair<int, int> >; _Alloc = std::allocator<std::pair<const std::pair<int, int>, int> >; std::map<_Key, _Tp, _Compare, _Alloc>::size_type = long unsigned int; std::map<_Key, _Tp, _Compare, _Alloc>::key_type = std::pair<int, int>]'
 1068 |       erase(const key_type& __x)
      |       ^~~~~
/usr/include/c++/10/bits/stl_map.h:1068:29: note:   no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'const key_type&' {aka 'const std::pair<int, int>&'}
 1068 |       erase(const key_type& __x)
      |             ~~~~~~~~~~~~~~~~^~~
/usr/include/c++/10/bits/stl_map.h:1088:7: note: candidate: 'std::map<_Key, _Tp, _Compare, _Alloc>::iterator std::map<_Key, _Tp, _Compare, _Alloc>::erase(std::map<_Key, _Tp, _Compare, _Alloc>::const_iterator, std::map<_Key, _Tp, _Compare, _Alloc>::const_iterator) [with _Key = std::pair<int, int>; _Tp = int; _Compare = std::less<std::pair<int, int> >; _Alloc = std::allocator<std::pair<const std::pair<int, int>, int> >; std::map<_Key, _Tp, _Compare, _Alloc>::iterator = std::_Rb_tree<std::pair<int, int>, std::pair<const std::pair<int, int>, int>, std::_Select1st<std::pair<const std::pair<int, int>, int> >, std::less<std::pair<int, int> >, std::allocator<std::pair<const std::pair<int, int>, int> > >::iterator; std::map<_Key, _Tp, _Compare, _Alloc>::const_iterator = std::_Rb_tree<std::pair<int, int>, std::pair<const std::pair<int, int>, int>, std::_Select1st<std::pair<const std::pair<int, int>, int> >, std::less<std::pair<int, int> >, std::allocator<std::pair<const std::pair<int, int>, int> > >::const_iterator]'
 1088 |       erase(const_iterator __first, const_iterator __last)
      |       ^~~~~
/usr/include/c++/10/bits/stl_map.h:1088:7: note:   candidate expects 2 arguments, 1 provided
collapse.cpp:114:24: error: 'T' was not declared in this scope
  114 |     for(int i = 0; i < T; ++i)
      |                        ^
collapse.cpp:116:17: error: 'W' was not declared in this scope
  116 |         int x = W[i], y = P[i];
      |                 ^
collapse.cpp:117:12: error: 'y' was not declared in this scope
  117 |         qr[y].push_back({x, i});
      |            ^
collapse.cpp:120:21: error: 'T' was not declared in this scope
  120 |     vector<int> ans(T); for(auto &i : ans) i = n;
      |                     ^