Submission #60847

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
60847	2018-07-24T20:45:42 Z	egorlifar	Collapse (JOI18_collapse)	C++17	Compilation error	0 ms	0 KB

collapse

#include "collapse.h"
#include <iostream>
#include <complex>
#include <vector>
#include <string>
#include <algorithm>
#include <cstdio>
#include <numeric>
#include <cstring>
#include <ctime>
#include <cstdlib>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <cmath>
#include <bitset>
#include <cassert>
#include <queue>
#include <stack>
#include <iomanip>
#include <deque>
    
     
using namespace std;
#define sz(c) (int)(c).size()
#define all(c) (c).begin(), (c).end()
#define rall(c) (c).rbegin(), (c).rend()
#define left left228
#define right right228
#define next next228
#define rank rank228
#define prev prev228
#define y1 y1228                                                         
#define read(FILENAME) freopen((FILENAME + ".in").c_str(), "r", stdin)
#define write(FILENAME) freopen((FILENAME + ".out").c_str(), "w", stdout)
#define files(FILENAME) read(FILENAME), write(FILENAME)
#define pb push_back
#define x first
#define y second
template<typename T1, typename T2>inline void chkmin(T1 &x, T2 y) { if (x > y) x = y; }
template<typename T1, typename T2>inline void chkmax(T1 &x, T2 y) { if (x < y) x = y; } 
const int block = 1000;

 
class DSU {
private:
	vector<int> parent;
	vector<int> rank;
	bool need;
	vector<int> change;
public:
	DSU(int n, bool need_ = false) : parent(n), rank(n, 0), need(need_) {
		for (int i = 0; i < n; i++) {
			parent[i] = i;
		}
	}
	int findset(int x) {
		if (parent[x] == x) {
			return x;
		}
		return parent[x] = findset(parent[x]);
	}
	bool setunion(int x, int y) {
		int xp = findset(x);
		int yp = findset(y);
		if (xp == yp) {
			return false;
		} else {
			if (need) {
				change.pb(xp);
				change.pb(yp);
			}
			if (rank[xp] > rank[yp]) {
				parent[yp] = xp;
			} else if (rank[xp] < rank[yp]) {
				parent[xp] = yp;
			} else {
				parent[yp] = xp;
				rank[xp]++;
			}
			return true;
		}
	}
	void reset() {
		for (auto i : change) {
			parent[i] = i;
			rank[i] = 0;
		}
		change.clear();
	}
};

 
vector<pair<int, int>> solve(
	int n,
	vector<pair<int, int> > fixed,
	vector<pair<int, pair<int, shared_ptr<vector<pair<int, int> >>>>> query
) {
	auto comp_second = [](const pair<int, int>& a, const pair<int, int>& b){ return a.second < b.second; };
	auto comp_first_only = [](const pair<int, pair<int, shared_ptr<vector<pair<int, int> >>>>& a, const pair<int, pair<int, shared_ptr<vector<pair<int, int> >>>>& b){ return a.first < b.first; };
	sort(all(fixed), comp_second);
	sort(all(query), comp_first_only);
	vector<pair<int, int> > ret;
	DSU large(n), tmp(n, true);
	int now = 0;
	int count = 0;
	for (auto i: query) {
		while (now < sz(fixed) && fixed[now].second <= i.first) {
			if (large.setunion(fixed[now].first, fixed[now].second)) {
				count++;
			}
			now++;
		}
		int c = count;
		for (auto j: *i.second.second) {
			if (j.second <= i.first && tmp.setunion(large.findset(j.first), large.findset(j.second))) {
				c++;
			}
		}
		ret.pb(make_pair(i.second.first, i.first + 1 - c));
		tmp.reset();
	}
	return ret;
}

 
pair<int, int> maxmin(int a, int b) {
	return make_pair(min(a, b), max(a, b));
}
 

pair<int, int> revp(int n, pair<int, int> p) {
	return make_pair(n - 1 - p.second, n - 1 - p.first);
}


vector<int> simulateCollapse(int N, vector<int> T, vector<int> X, vector<int> Y, vector<int> W, vector<int> P) {
	vector<pair<pair<int, int>, int>> q;
	for(int i = 0; i < sz(W); i++) {
		q.pb(make_pair(make_pair(W[i], P[i]), i));
	}
	sort(all(q));
	vector<int> ans(sz(q), 0);
	set<pair<int, int> > path;
	int now = 0;
	for(int s = 0; s < sz(T); s += block) {
		int e = min(s + block, sz(T));
		set<pair<int, int> > change;
		for (int i = s; i < e; i++) {
			change.insert(maxmin(X[i], Y[i]));
		}
		auto fixed = path;
		set<pair<int, int> > np;
		for(auto i: change) {
			if (fixed.find(i) != fixed.end()) {
				fixed.erase(i);
				np.insert(i);
			}
		}
		vector<pair<int, int> > fixed1, fixed2;
		for (auto i: fixed) {
			fixed1.pb(i);
			fixed2.pb(revp(N, i));
		}
		vector<pair<int, pair<int, shared_ptr<vector<pair<int, int> >> > > > query1, query2;
		for (int i = s; i < e; i++) {
			if (T[i] == 0) {
				path.insert(maxmin(X[i], Y[i]));
				np.insert(maxmin(X[i], Y[i]));
			} else {
				path.erase(maxmin(X[i], Y[i]));
				np.erase(maxmin(X[i], Y[i]));
			}
			shared_ptr<vector<pair<int, int> > > p1(new vector<pair<int, int> >), p2(new vector<pair<int, int> >);
			for (auto j: np) {
				p1->pb(j);
				p2->pb(revp(N, j));
			}
			while (now < sz(q) && q[now].first.first == i) {
				query1.pb(make_pair(q[now].first.second, make_pair(q[now].second, p1)));
				query2.pb(make_pair(N - 2 - q[now].first.second, make_pair(q[now].second, p2)));
				now++;
			}
		}
		for (auto x: solve(N, fixed1, query1)) {
			ans[x.first] += x.second;
		}
		for (auto x: solve(N, fixed2, query2)) {
			ans[x.first] += x.second;
		}
	}
	return ans;
}

Compilation message

collapse.cpp:99:29: error: 'shared_ptr' was not declared in this scope
  vector<pair<int, pair<int, shared_ptr<vector<pair<int, int> >>>>> query
                             ^~~~~~~~~~
collapse.cpp:99:29: note: suggested alternative: 'char16_t'
  vector<pair<int, pair<int, shared_ptr<vector<pair<int, int> >>>>> query
                             ^~~~~~~~~~
                             char16_t
collapse.cpp:99:62: error: template argument 2 is invalid
  vector<pair<int, pair<int, shared_ptr<vector<pair<int, int> >>>>> query
                                                              ^~
collapse.cpp:99:29: error: 'shared_ptr' was not declared in this scope
  vector<pair<int, pair<int, shared_ptr<vector<pair<int, int> >>>>> query
                             ^~~~~~~~~~
collapse.cpp:99:29: note: suggested alternative: 'char16_t'
  vector<pair<int, pair<int, shared_ptr<vector<pair<int, int> >>>>> query
                             ^~~~~~~~~~
                             char16_t
collapse.cpp:99:62: error: template argument 2 is invalid
  vector<pair<int, pair<int, shared_ptr<vector<pair<int, int> >>>>> query
                                                              ^~
collapse.cpp:99:29: error: 'shared_ptr' was not declared in this scope
  vector<pair<int, pair<int, shared_ptr<vector<pair<int, int> >>>>> query
                             ^~~~~~~~~~
collapse.cpp:99:29: note: suggested alternative: 'char16_t'
  vector<pair<int, pair<int, shared_ptr<vector<pair<int, int> >>>>> query
                             ^~~~~~~~~~
                             char16_t
collapse.cpp:99:62: error: template argument 2 is invalid
  vector<pair<int, pair<int, shared_ptr<vector<pair<int, int> >>>>> query
                                                              ^~
collapse.cpp:99:29: error: 'shared_ptr' was not declared in this scope
  vector<pair<int, pair<int, shared_ptr<vector<pair<int, int> >>>>> query
                             ^~~~~~~~~~
collapse.cpp:99:29: note: suggested alternative: 'char16_t'
  vector<pair<int, pair<int, shared_ptr<vector<pair<int, int> >>>>> query
                             ^~~~~~~~~~
                             char16_t
collapse.cpp:99:62: error: template argument 2 is invalid
  vector<pair<int, pair<int, shared_ptr<vector<pair<int, int> >>>>> query
                                                              ^~
collapse.cpp:99:19: error: invalid template-id
  vector<pair<int, pair<int, shared_ptr<vector<pair<int, int> >>>>> query
                   ^~~~
collapse.cpp:99:29: error: 'shared_ptr' was not declared in this scope
  vector<pair<int, pair<int, shared_ptr<vector<pair<int, int> >>>>> query
                             ^~~~~~~~~~
collapse.cpp:99:29: note: suggested alternative: 'char16_t'
  vector<pair<int, pair<int, shared_ptr<vector<pair<int, int> >>>>> query
                             ^~~~~~~~~~
                             char16_t
collapse.cpp:99:19: error: type/value mismatch at argument 2 in template parameter list for 'template<class _T1, class _T2> struct std::pair'
  vector<pair<int, pair<int, shared_ptr<vector<pair<int, int> >>>>> query
                   ^~~~
collapse.cpp:99:19: note:   expected a type, got 'pair'
collapse.cpp:99:64: error: template argument 1 is invalid
  vector<pair<int, pair<int, shared_ptr<vector<pair<int, int> >>>>> query
                                                                ^~
collapse.cpp:99:64: error: template argument 2 is invalid
collapse.cpp:99:66: error: expected ',' or '...' before '>' token
  vector<pair<int, pair<int, shared_ptr<vector<pair<int, int> >>>>> query
                                                                  ^
collapse.cpp: In function 'std::vector<std::pair<int, int> > solve(int, std::vector<std::pair<int, int> >, int)':
collapse.cpp:102:54: error: 'shared_ptr' was not declared in this scope
  auto comp_first_only = [](const pair<int, pair<int, shared_ptr<vector<pair<int, int> >>>>& a, const pair<int, pair<int, shared_ptr<vector<pair<int, int> >>>>& b){ return a.first < b.first; };
                                                      ^~~~~~~~~~
collapse.cpp:102:54: note: suggested alternative: 'char16_t'
  auto comp_first_only = [](const pair<int, pair<int, shared_ptr<vector<pair<int, int> >>>>& a, const pair<int, pair<int, shared_ptr<vector<pair<int, int> >>>>& b){ return a.first < b.first; };
                                                      ^~~~~~~~~~
                                                      char16_t
collapse.cpp:102:87: error: template argument 2 is invalid
  auto comp_first_only = [](const pair<int, pair<int, shared_ptr<vector<pair<int, int> >>>>& a, const pair<int, pair<int, shared_ptr<vector<pair<int, int> >>>>& b){ return a.first < b.first; };
                                                                                       ^~
collapse.cpp:102:44: error: template argument 2 is invalid
  auto comp_first_only = [](const pair<int, pair<int, shared_ptr<vector<pair<int, int> >>>>& a, const pair<int, pair<int, shared_ptr<vector<pair<int, int> >>>>& b){ return a.first < b.first; };
                                            ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
collapse.cpp:102:89: error: expected ',' or '...' before '>' token
  auto comp_first_only = [](const pair<int, pair<int, shared_ptr<vector<pair<int, int> >>>>& a, const pair<int, pair<int, shared_ptr<vector<pair<int, int> >>>>& b){ return a.first < b.first; };
                                                                                         ^~
collapse.cpp: In lambda function:
collapse.cpp:102:172: error: 'a' was not declared in this scope
  auto comp_first_only = [](const pair<int, pair<int, shared_ptr<vector<pair<int, int> >>>>& a, const pair<int, pair<int, shared_ptr<vector<pair<int, int> >>>>& b){ return a.first < b.first; };
                                                                                                                                                                            ^
collapse.cpp:102:182: error: 'b' was not declared in this scope
  auto comp_first_only = [](const pair<int, pair<int, shared_ptr<vector<pair<int, int> >>>>& a, const pair<int, pair<int, shared_ptr<vector<pair<int, int> >>>>& b){ return a.first < b.first; };
                                                                                                                                                                                      ^
collapse.cpp: In function 'std::vector<std::pair<int, int> > solve(int, std::vector<std::pair<int, int> >, int)':
collapse.cpp:104:11: error: 'query' was not declared in this scope
  sort(all(query), comp_first_only);
           ^
collapse.cpp:28:17: note: in definition of macro 'all'
 #define all(c) (c).begin(), (c).end()
                 ^
collapse.cpp:109:15: error: unable to deduce 'auto&&' from 'query'
  for (auto i: query) {
               ^~~~~
collapse.cpp: In function 'std::vector<int> simulateCollapse(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
collapse.cpp:167:30: error: 'shared_ptr' was not declared in this scope
   vector<pair<int, pair<int, shared_ptr<vector<pair<int, int> >> > > > query1, query2;
                              ^~~~~~~~~~
collapse.cpp:167:30: note: suggested alternative: 'char16_t'
   vector<pair<int, pair<int, shared_ptr<vector<pair<int, int> >> > > > query1, query2;
                              ^~~~~~~~~~
                              char16_t
collapse.cpp:167:63: error: template argument 2 is invalid
   vector<pair<int, pair<int, shared_ptr<vector<pair<int, int> >> > > > query1, query2;
                                                               ^~
collapse.cpp:167:66: error: template argument 2 is invalid
   vector<pair<int, pair<int, shared_ptr<vector<pair<int, int> >> > > > query1, query2;
                                                                  ^
collapse.cpp:167:68: error: template argument 1 is invalid
   vector<pair<int, pair<int, shared_ptr<vector<pair<int, int> >> > > > query1, query2;
                                                                    ^
collapse.cpp:167:68: error: template argument 2 is invalid
collapse.cpp:167:70: error: expected unqualified-id before '>' token
   vector<pair<int, pair<int, shared_ptr<vector<pair<int, int> >> > > > query1, query2;
                                                                      ^
collapse.cpp:176:39: error: expected primary-expression before '>' token
    shared_ptr<vector<pair<int, int> > > p1(new vector<pair<int, int> >), p2(new vector<pair<int, int> >);
                                       ^
collapse.cpp:176:41: error: 'p1' was not declared in this scope
    shared_ptr<vector<pair<int, int> > > p1(new vector<pair<int, int> >), p2(new vector<pair<int, int> >);
                                         ^~
collapse.cpp:176:41: note: suggested alternative: 'y1'
    shared_ptr<vector<pair<int, int> > > p1(new vector<pair<int, int> >), p2(new vector<pair<int, int> >);
                                         ^~
                                         y1
collapse.cpp:176:74: error: 'p2' was not declared in this scope
    shared_ptr<vector<pair<int, int> > > p1(new vector<pair<int, int> >), p2(new vector<pair<int, int> >);
                                                                          ^~
collapse.cpp:176:74: note: suggested alternative: 'pb'
    shared_ptr<vector<pair<int, int> > > p1(new vector<pair<int, int> >), p2(new vector<pair<int, int> >);
                                                                          ^~
                                                                          pb
collapse.cpp:182:5: error: 'query1' was not declared in this scope
     query1.pb(make_pair(q[now].first.second, make_pair(q[now].second, p1)));
     ^~~~~~
collapse.cpp:183:5: error: 'query2' was not declared in this scope
     query2.pb(make_pair(N - 2 - q[now].first.second, make_pair(q[now].second, p2)));
     ^~~~~~
collapse.cpp:187:33: error: 'query1' was not declared in this scope
   for (auto x: solve(N, fixed1, query1)) {
                                 ^~~~~~
collapse.cpp:190:33: error: 'query2' was not declared in this scope
   for (auto x: solve(N, fixed2, query2)) {
                                 ^~~~~~