oj.uz

Submission #65798

# Submission time Handle Problem Language Result Execution time Memory
65798 2018-08-08T21:43:57 Z Benq Collapse (JOI18_collapse) C++11
Compilation error
 0 ms 0 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
 
using namespace std;
using namespace __gnu_pbds;
 
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;
 
typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;
 
typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;
 
template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;
 
#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)
 
#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
 
const int MOD = 1000000007;
const ll INF = 1e18;
const int MX = 100001;
 
// #define LOCAL 
 
#ifdef LOCAL 
#else 
    #include "collapse.h"
#endif
 
const int BLOCK = 1000;
 
int N;
 
template<int SZ> struct realDSU {
    int par[SZ], numComp = 0;
    void init(int co) {
        F0R(i,co) par[i] = i;
    }
    
    int get(int x) { // path compression
    	if (par[x] != x) par[x] = get(par[x]);
    	return par[x];
    }
    bool unite(int x, int y) {
        x = get(x), y = get(y);
        if (x == y) return 0;
        if (rand()&1) swap(x,y);
        par[y] = x; numComp --;
        return 1;
    }
};

vi ans;
vector<array<int,3>> change;
vpi tri[MX];
unordered_set<int> from[MX], to[MX];
 
unordered_map<ll,int> u;
vpi ru;

ll hsh(pi cur) { return (ll)cur.f*MX+cur.s; }

int m[MX];
realDSU<2*BLOCK> R;
int mini(const vpi& v) {
    int co = 0;
    for (auto a: v) m[a.f] = m[a.s] = -1;
    for (auto a: v) {
        if (m[a.f] == -1) m[a.f] = co ++;
        if (m[a.s] == -1) m[a.s] = co ++;
    }
    R.init(co);
    int res = 0;
    for (auto a: v) 
    	if (R.unite(m[a.f],m[a.s])) res ++;
    return res;
}
 
vector<pair<pi,bitset<BLOCK>>> todo;
 
void solveA() {
	realDSU<MX> A = realDSU<MX>(); 
	A.init(N);
	
    int ind = 0;
    F0R(i,N) {
        A.numComp ++;
    	for (int x: to[i]) A.unite(x,i);
        while (ind < sz(todo) && todo[ind].f.f == i) {
        	ans[todo[ind].f.s] += A.numComp;
        	
        	vpi tmp;
        	F0R(j,sz(ru)) if (todo[ind].s[j] == 1 && ru[j].s <= i)
        		tmp.pb({A.get(ru[j].f),A.get(ru[j].s)});
        		
        	ans[todo[ind].f.s] -= mini(tmp);
        	ind ++;
        }
    }
}
 
void solveB() {
	realDSU<MX> B = realDSU<MX>();
	B.init(N);
	
	int ind = 0;
    F0R(i,N) {
        B.numComp ++;
        for (int x: from[N-1-i]) B.unite(x,N-1-i);
        while (ind < sz(todo) && todo[ind].f.f+1 == N-1-i) {
        	ans[todo[ind].f.s] += B.numComp;
        	
        	vpi tmp;
        	F0R(j,sz(ru)) if (todo[ind].s[j] == 1 && ru[j].f >= N-1-i)
        		tmp.pb({B.get(ru[j].f),B.get(ru[j].s)});
        		
        	ans[todo[ind].f.s] -= mini(tmp);
        	ind ++;
        }
    }
}
 
void genDSU() {
    sort(all(todo),[](const auto& a, const auto& b) { return a.f < b.f;});
    solveA();
    reverse(all(todo)); 
    solveB();
	todo.clear();
}

void process(int l, int r) {
	u.clear(), ru.clear();
	bitset<BLOCK> b = bitset<BLOCK>();
    FOR(i,l,r+1) {
        pi cur = {change[i][1],change[i][2]};
        if (!u.count((ll)cur.f*MX+cur.s)) {
        	int t = sz(u);
        	u[hsh(cur)] = t;
        	ru.pb(cur);
        }
        if (from[cur.f].count(cur.s)) {
        	from[cur.f].erase(cur.s); to[cur.s].erase(cur.f);
            b[u[hsh(cur)]] = 1;
        }
    }
    FOR(i,l,r+1) {
        pi cur = {change[i][1],change[i][2]};
        if (change[i][0] == 0) b[u[hsh(cur)]] = 1;
        else b[u[hsh(cur)]] = 0;
        for (auto a: tri[i]) todo.pb({a,b});
    }
    genDSU();
    F0R(i,sz(ru)) if (b[i] == 1) {
    	pi a = ru[i];
    	from[a.f].insert(a.s), to[a.s].insert(a.f);
    }
}
 
vi simulateCollapse(int n, vi T, vi X, vi Y, vi W, vi P) {
    N = n; 
    
    F0R(i,sz(X)) {
        if (X[i] > Y[i]) swap(X[i],Y[i]);
        change.pb({T[i],X[i],Y[i]});
    }
    
    ans.resize(sz(W));
    F0R(i,sz(ans)) tri[W[i]].pb({P[i],i});
    
    for (int i = 0; i < sz(X); i += BLOCK) process(i,min(i+BLOCK,sz(X))-1);
    return ans;
}
 
#ifdef LOCAL 
 
int main(int argc, char *argv[]) {
	int N, C, Q;
	//cin >> N;
	//C = Q = N; 
	scanf("%d%d%d", &N, &C, &Q);
	std::vector<int> T(C), X(C), Y(C);
	for(int i = 0; i < C; i++) {
		// T[i] = 0; X[i] = rand() % N, Y[i] = rand() % N;
		scanf("%d%d%d", &T[i], &X[i], &Y[i]);
	}
	std::vector<int> W(Q), P(Q);
	for(int i = 0; i < Q; i++) {
		// W[i] = rand() % N; P[i] = rand() % (N-1);
		scanf("%d%d", &W[i], &P[i]);
	}
	auto res = simulateCollapse(N, T, X, Y, W, P);
	printf("%d\n",Q);
	for(auto i : res) {
		printf("%d\n", i);
	}
}
 
/*
5 8 2
0 0 1
0 1 3
0 2 4
0 4 0
1 1 3
0 0 3
0 1 2
0 4 3
3 1
7 3
*/
#endif
 
 
/* Look for:
* the exact constraints (multiple sets are too slow for n=10^6 :( ) 
* special cases (n=1?)
* overflow (ll vs int?)
* array bounds
*/

Compilation message

collapse.cpp: In function 'void genDSU()':
collapse.cpp:144:29: error: use of 'auto' in lambda parameter declaration only available with -std=c++14 or -std=gnu++14
     sort(all(todo),[](const auto& a, const auto& b) { return a.f < b.f;});
                             ^~~~
collapse.cpp:144:44: error: use of 'auto' in lambda parameter declaration only available with -std=c++14 or -std=gnu++14
     sort(all(todo),[](const auto& a, const auto& b) { return a.f < b.f;});
                                            ^~~~
collapse.cpp: In lambda function:
collapse.cpp:33:11: error: request for member 'first' in 'a', which is of non-class type 'const int'
 #define f first
           ^
collapse.cpp:144:64: note: in expansion of macro 'f'
     sort(all(todo),[](const auto& a, const auto& b) { return a.f < b.f;});
                                                                ^
collapse.cpp:33:11: error: request for member 'first' in 'b', which is of non-class type 'const int'
 #define f first
           ^
collapse.cpp:144:70: note: in expansion of macro 'f'
     sort(all(todo),[](const auto& a, const auto& b) { return a.f < b.f;});
                                                                      ^
In file included from /usr/include/c++/7/bits/stl_algobase.h:71:0,
                 from /usr/include/c++/7/bits/char_traits.h:39,
                 from /usr/include/c++/7/ios:40,
                 from /usr/include/c++/7/istream:38,
                 from /usr/include/c++/7/sstream:38,
                 from /usr/include/c++/7/complex:45,
                 from /usr/include/c++/7/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
                 from collapse.cpp:1:
/usr/include/c++/7/bits/predefined_ops.h: In instantiation of 'bool __gnu_cxx::__ops::_Iter_comp_iter<_Compare>::operator()(_Iterator1, _Iterator2) [with _Iterator1 = __gnu_cxx::__normal_iterator<std::pair<std::pair<int, int>, std::bitset<1000> >*, std::vector<std::pair<std::pair<int, int>, std::bitset<1000> > > >; _Iterator2 = __gnu_cxx::__normal_iterator<std::pair<std::pair<int, int>, std::bitset<1000> >*, std::vector<std::pair<std::pair<int, int>, std::bitset<1000> > > >; _Compare = genDSU()::<lambda(const int&, const int&)>]':
/usr/include/c++/7/bits/stl_algo.h:1847:14:   required from 'void std::__insertion_sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<std::pair<std::pair<int, int>, std::bitset<1000> >*, std::vector<std::pair<std::pair<int, int>, std::bitset<1000> > > >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<genDSU()::<lambda(const int&, const int&)> >]'
/usr/include/c++/7/bits/stl_algo.h:1885:25:   required from 'void std::__final_insertion_sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<std::pair<std::pair<int, int>, std::bitset<1000> >*, std::vector<std::pair<std::pair<int, int>, std::bitset<1000> > > >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<genDSU()::<lambda(const int&, const int&)> >]'
/usr/include/c++/7/bits/stl_algo.h:1971:31:   required from 'void std::__sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<std::pair<std::pair<int, int>, std::bitset<1000> >*, std::vector<std::pair<std::pair<int, int>, std::bitset<1000> > > >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<genDSU()::<lambda(const int&, const int&)> >]'
/usr/include/c++/7/bits/stl_algo.h:4868:18:   required from 'void std::sort(_RAIter, _RAIter, _Compare) [with _RAIter = __gnu_cxx::__normal_iterator<std::pair<std::pair<int, int>, std::bitset<1000> >*, std::vector<std::pair<std::pair<int, int>, std::bitset<1000> > > >; _Compare = genDSU()::<lambda(const int&, const int&)>]'
collapse.cpp:144:73:   required from here
/usr/include/c++/7/bits/predefined_ops.h:143:18: error: no match for call to '(genDSU()::<lambda(const int&, const int&)>) (std::pair<std::pair<int, int>, std::bitset<1000> >&, std::pair<std::pair<int, int>, std::bitset<1000> >&)'
         { return bool(_M_comp(*__it1, *__it2)); }
                  ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/7/bits/predefined_ops.h:143:18: note: candidate: void (*)(const int&, const int&) <conversion>
/usr/include/c++/7/bits/predefined_ops.h:143:18: note:   candidate expects 3 arguments, 3 provided
collapse.cpp:144:51: note: candidate: genDSU()::<lambda(const int&, const int&)>
     sort(all(todo),[](const auto& a, const auto& b) { return a.f < b.f;});
                                                   ^
collapse.cpp:144:51: note:   no known conversion for argument 1 from 'std::pair<std::pair<int, int>, std::bitset<1000> >' to 'const int&'
In file included from /usr/include/c++/7/bits/stl_algobase.h:71:0,
                 from /usr/include/c++/7/bits/char_traits.h:39,
                 from /usr/include/c++/7/ios:40,
                 from /usr/include/c++/7/istream:38,
                 from /usr/include/c++/7/sstream:38,
                 from /usr/include/c++/7/complex:45,
                 from /usr/include/c++/7/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
                 from collapse.cpp:1:
/usr/include/c++/7/bits/predefined_ops.h: In instantiation of 'bool __gnu_cxx::__ops::_Val_comp_iter<_Compare>::operator()(_Value&, _Iterator) [with _Value = std::pair<std::pair<int, int>, std::bitset<1000> >; _Iterator = __gnu_cxx::__normal_iterator<std::pair<std::pair<int, int>, std::bitset<1000> >*, std::vector<std::pair<std::pair<int, int>, std::bitset<1000> > > >; _Compare = genDSU()::<lambda(const int&, const int&)>]':
/usr/include/c++/7/bits/stl_algo.h:1828:20:   required from 'void std::__unguarded_linear_insert(_RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<std::pair<std::pair<int, int>, std::bitset<1000> >*, std::vector<std::pair<std::pair<int, int>, std::bitset<1000> > > >; _Compare = __gnu_cxx::__ops::_Val_comp_iter<genDSU()::<lambda(const int&, const int&)> >]'
/usr/include/c++/7/bits/stl_algo.h:1855:36:   required from 'void std::__insertion_sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<std::pair<std::pair<int, int>, std::bitset<1000> >*, std::vector<std::pair<std::pair<int, int>, std::bitset<1000> > > >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<genDSU()::<lambda(const int&, const int&)> >]'
/usr/include/c++/7/bits/stl_algo.h:1885:25:   required from 'void std::__final_insertion_sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<std::pair<std::pair<int, int>, std::bitset<1000> >*, std::vector<std::pair<std::pair<int, int>, std::bitset<1000> > > >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<genDSU()::<lambda(const int&, const int&)> >]'
/usr/include/c++/7/bits/stl_algo.h:1971:31:   required from 'void std::__sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<std::pair<std::pair<int, int>, std::bitset<1000> >*, std::vector<std::pair<std::pair<int, int>, std::bitset<1000> > > >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<genDSU()::<lambda(const int&, const int&)> >]'
/usr/include/c++/7/bits/stl_algo.h:4868:18:   required from 'void std::sort(_RAIter, _RAIter, _Compare) [with _RAIter = __gnu_cxx::__normal_iterator<std::pair<std::pair<int, int>, std::bitset<1000> >*, std::vector<std::pair<std::pair<int, int>, std::bitset<1000> > > >; _Compare = genDSU()::<lambda(const int&, const int&)>]'
collapse.cpp:144:73:   required from here
/usr/include/c++/7/bits/predefined_ops.h:215:11: error: no match for call to '(genDSU()::<lambda(const int&, const int&)>) (std::pair<std::pair<int, int>, std::bitset<1000> >&, std::pair<std::pair<int, int>, std::bitset<1000> >&)'
  { return bool(_M_comp(__val, *__it)); }
           ^~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/7/bits/predefined_ops.h:215:11: note: candidate: void (*)(const int&, const int&) <conversion>
/usr/include/c++/7/bits/predefined_ops.h:215:11: note:   candidate expects 3 arguments, 3 provided
collapse.cpp:144:51: note: candidate: genDSU()::<lambda(const int&, const int&)>
     sort(all(todo),[](const auto& a, const auto& b) { return a.f < b.f;});
                                                   ^
collapse.cpp:144:51: note:   no known conversion for argument 1 from 'std::pair<std::pair<int, int>, std::bitset<1000> >' to 'const int&'
In file included from /usr/include/c++/7/bits/stl_algobase.h:71:0,
                 from /usr/include/c++/7/bits/char_traits.h:39,
                 from /usr/include/c++/7/ios:40,
                 from /usr/include/c++/7/istream:38,
                 from /usr/include/c++/7/sstream:38,
                 from /usr/include/c++/7/complex:45,
                 from /usr/include/c++/7/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
                 from collapse.cpp:1:
/usr/include/c++/7/bits/predefined_ops.h: In instantiation of 'bool __gnu_cxx::__ops::_Iter_comp_val<_Compare>::operator()(_Iterator, _Value&) [with _Iterator = __gnu_cxx::__normal_iterator<std::pair<std::pair<int, int>, std::bitset<1000> >*, std::vector<std::pair<std::pair<int, int>, std::bitset<1000> > > >; _Value = std::pair<std::pair<int, int>, std::bitset<1000> >; _Compare = genDSU()::<lambda(const int&, const int&)>]':
/usr/include/c++/7/bits/stl_heap.h:133:48:   required from 'void std::__push_heap(_RandomAccessIterator, _Distance, _Distance, _Tp, _Compare&) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<std::pair<std::pair<int, int>, std::bitset<1000> >*, std::vector<std::pair<std::pair<int, int>, std::bitset<1000> > > >; _Distance = long int; _Tp = std::pair<std::pair<int, int>, std::bitset<1000> >; _Compare = __gnu_cxx::__ops::_Iter_comp_val<genDSU()::<lambda(const int&, const int&)> >]'
/usr/include/c++/7/bits/stl_heap.h:237:23:   required from 'void std::__adjust_heap(_RandomAccessIterator, _Distance, _Distance, _Tp, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<std::pair<std::pair<int, int>, std::bitset<1000> >*, std::vector<std::pair<std::pair<int, int>, std::bitset<1000> > > >; _Distance = long int; _Tp = std::pair<std::pair<int, int>, std::bitset<1000> >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<genDSU()::<lambda(const int&, const int&)> >]'
/usr/include/c++/7/bits/stl_heap.h:342:22:   required from 'void std::__make_heap(_RandomAccessIterator, _RandomAccessIterator, _Compare&) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<std::pair<std::pair<int, int>, std::bitset<1000> >*, std::vector<std::pair<std::pair<int, int>, std::bitset<1000> > > >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<genDSU()::<lambda(const int&, const int&)> >]'
/usr/include/c++/7/bits/stl_algo.h:1672:23:   required from 'void std::__heap_select(_RandomAccessIterator, _RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<std::pair<std::pair<int, int>, std::bitset<1000> >*, std::vector<std::pair<std::pair<int, int>, std::bitset<1000> > > >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<genDSU()::<lambda(const int&, const int&)> >]'
/usr/include/c++/7/bits/stl_algo.h:1933:25:   required from 'void std::__partial_sort(_RandomAccessIterator, _RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<std::pair<std::pair<int, int>, std::bitset<1000> >*, std::vector<std::pair<std::pair<int, int>, std::bitset<1000> > > >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<genDSU()::<lambda(const int&, const int&)> >]'
/usr/include/c++/7/bits/stl_algo.h:1948:27:   required from 'void std::__introsort_loop(_RandomAccessIterator, _RandomAccessIterator, _Size, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<std::pair<std::pair<int, int>, std::bitset<1000> >*, std::vector<std::pair<std::pair<int, int>, std::bitset<1000> > > >; _Size = long int; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<genDSU()::<lambda(const int&, const int&)> >]'
/usr/include/c++/7/bits/stl_algo.h:1968:25:   required from 'void std::__sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<std::pair<std::pair<int, int>, std::bitset<1000> >*, std::vector<std::pair<std::pair<int, int>, std::bitset<1000> > > >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<genDSU()::<lambda(const int&, const int&)> >]'
/usr/include/c++/7/bits/stl_algo.h:4868:18:   required from 'void std::sort(_RAIter, _RAIter, _Compare) [with _RAIter = __gnu_cxx::__normal_iterator<std::pair<std::pair<int, int>, std::bitset<1000> >*, std::vector<std::pair<std::pair<int, int>, std::bitset<1000> > > >; _Compare = genDSU()::<lambda(const int&, const int&)>]'
collapse.cpp:144:73:   required from here
/usr/include/c++/7/bits/predefined_ops.h:177:11: error: no match for call to '(genDSU()::<lambda(const int&, const int&)>) (std::pair<std::pair<int, int>, std::bitset<1000> >&, std::pair<std::pair<int, int>, std::bitset<1000> >&)'
  { return bool(_M_comp(*__it, __val)); }
           ^~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/7/bits/predefined_ops.h:177:11: note: candidate: void (*)(const int&, const int&) <conversion>
/usr/include/c++/7/bits/predefined_ops.h:177:11: note:   candidate expects 3 arguments, 3 provided
collapse.cpp:144:51: note: candidate: genDSU()::<lambda(const int&, const int&)>
     sort(all(todo),[](const auto& a, const auto& b) { return a.f < b.f;});
                                                   ^
collapse.cpp:144:51: note:   no known conversion for argument 1 from 'std::pair<std::pair<int, int>, std::bitset<1000> >' to 'const int&'