Submission #102196

# Submission time Handle Problem Language Result Execution time Memory
102196 2019-03-23T11:07:48 Z Minnakhmetov Collapse (JOI18_collapse) C++14
Compilation error
0 ms 0 KB
#include "collapse.h"

struct E {
	int x, y, i;
	bool operator < (const E &oth) const {
		return x < oth.x;
	}
};

struct Q {
	int t, type, i, x;
	bool operator < (const Q &oth) const {
		return t == oth.t ? type : t < oth.t;
	}
};

const int N = 1e5 + 5, Z = 350;
bool isOn[N], usedv[N], usede[N];
int par[N];
vector<E> edges, se1, se2;
map<pair<int, int>, int> mp_e;
vector<int> ans;
map<int, vector<pair<int, int>>> mp;
int n, m;

#define all(aaa) aaa.begin(), aaa.end()

int findSet(int v) {
	return par[v] == v ? v : par[v] = findSet(par[v]);
}

bool un(int x, int y) {
	x = findSet(x);
	y = findSet(y);
	if (x == y)
		return false;
	if (usedv[y])
		swap(x, y);
	par[y] = x;
	return true;
}

void solve(vector<Q> qr) {
	fill(usedv, usedv + N, false);
	mp.clear();

	vector<Q> s;
	vector<E> ve;
	vector<int> vtx;
	
	for (Q q : qr) {
		if (q.type) {
			usede[q.i] = usedv[edges[q.i].x] = 
				usedv[edges[q.i].y] = 1;
		}
		else {
			s.push_back(q);
		}
	}

	for (int i = 0; i < n; i++) {
		if (usedv[i]) {
			vtx.push_back(i);
		}
	}

	for (int i = 0; i < m; i++) {
		if (usede[i]) {
			ve.push_back(edges[i]);
		}
	}

	sort(all(s), [](Q &a, Q &b) {
		return a.x < b.x;
	});

	for (int i = 0; i < n; i++) {
		par[i] = i;
	}

	for (int i = 0, j = 0, r = 0; i < s.size(); i++) {
		while (j < se1.size() && se1[j].x <= s[i].x) {
			if (!usede[se1[j].i] && isOn[se1[j].i])
				r += un(se1[j].x, se1[j].y);
			j++;
		}
		ans[s[i].i] -= r;
		for (int k : vtx) {
			if (k <= s[i].x)
				mp[s[i].i].push_back({ k, findSet(k) });
		}
	}

	for (int i = 0; i < n; i++) {
		par[i] = i;
	}

	for (int i = 0, j = 0, r = 0; i < s.size(); i++) {
		while (j < se2.size() && se2[j].x > s[i].x) {
			if (!usede[se2[j].i] && isOn[se2[j].i])
				r += un(se2[j].x, se2[j].y);
			j++;
		}
		ans[s[i].i] -= r;
		for (int k : vtx) {
			if (k > s[i].x)
				mp[s[i].i].push_back({ k, findSet(k) });
		}
	}

	for (Q q : qr) {
		if (q.type) {
			isOn[q.i] ^= 1;
		}
		else {
			for (auto p : mp[q.i])
				par[p.first] = p.second;
			for (E e : ve) {
				if (isOn[e.i] &&
					(e.x <= q.x || e.y > q.x)) {
					ans[q.i] -= un(e.x, e.y);
				}
			}
		}
	}
}

vector<int> simulateCollapse(
	int _n,
	vector<int> T,
	vector<int> X,
	vector<int> Y,
	vector<int> W,
	vector<int> P
) {
	n = _n;
	m = T.size();
	
	int q = W.size();
	vector<Q> v;

	for (int i = 0; i < m; i++) {
		if (X[i] < Y[i])
			swap(X[i], Y[i]);
		if (!mp_e.count({ X[i], Y[i] })) {
			mp_e[{X[i], Y[i]}] = edges.size();
			edges.push_back({ X[i], Y[i], i });
		}
		se1.push_back({ X[i], Y[i], i });
		se2.push_back({ Y[i], X[i], i });
		v.push_back({ i, 1, mp_e[{X[i], Y[i]}] });
	}

	sort(all(se1));
	sort(all(se2));
	reverse(all(se2));

	ans.resize(q, _n);

	for (int i = 0; i < q; i++) {
		v.push_back({ W[i], 0, i, P[i] });
	}

	sort(all(v));

	for (int i = 0; i < v.size(); i++) {
		if (i % Z == 0) {
			solve(vector<Q>(v.begin() + i, v.begin() + min((int)v.size(), i + Z)));
		}
	}

	return ans;
}

Compilation message

collapse.cpp:20:1: error: 'vector' does not name a type
 vector<E> edges, se1, se2;
 ^~~~~~
collapse.cpp:21:1: error: 'map' does not name a type
 map<pair<int, int>, int> mp_e;
 ^~~
collapse.cpp:22:1: error: 'vector' does not name a type
 vector<int> ans;
 ^~~~~~
collapse.cpp:23:1: error: 'map' does not name a type
 map<int, vector<pair<int, int>>> mp;
 ^~~
collapse.cpp: In function 'bool un(int, int)':
collapse.cpp:38:3: error: 'swap' was not declared in this scope
   swap(x, y);
   ^~~~
collapse.cpp:38:3: note: suggested alternatives:
In file included from /usr/include/c++/7/vector:65:0,
                 from collapse.h:5,
                 from collapse.cpp:1:
/usr/include/c++/7/bits/stl_bvector.h:128:3: note:   'std::swap'
   swap(bool& __x, _Bit_reference __y) noexcept
   ^~~~
In file included from /usr/include/c++/7/bits/stl_pair.h:59:0,
                 from /usr/include/c++/7/bits/stl_algobase.h:64,
                 from /usr/include/c++/7/vector:60,
                 from collapse.h:5,
                 from collapse.cpp:1:
/usr/include/c++/7/bits/move.h:187:5: note:   'std::swap'
     swap(_Tp& __a, _Tp& __b)
     ^~~~
In file included from /usr/include/c++/7/exception:142:0,
                 from /usr/include/c++/7/new:40,
                 from /usr/include/c++/7/ext/new_allocator.h:33,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/c++allocator.h:33,
                 from /usr/include/c++/7/bits/allocator.h:46,
                 from /usr/include/c++/7/vector:61,
                 from collapse.h:5,
                 from collapse.cpp:1:
/usr/include/c++/7/bits/exception_ptr.h:166:5: note:   'std::__exception_ptr::swap'
     swap(exception_ptr& __lhs, exception_ptr& __rhs)
     ^~~~
collapse.cpp: At global scope:
collapse.cpp:43:12: error: variable or field 'solve' declared void
 void solve(vector<Q> qr) {
            ^~~~~~
collapse.cpp:43:12: error: 'vector' was not declared in this scope
collapse.cpp:43:12: note: suggested alternative:
In file included from /usr/include/c++/7/vector:64:0,
                 from collapse.h:5,
                 from collapse.cpp:1:
/usr/include/c++/7/bits/stl_vector.h:216:11: note:   'std::vector'
     class vector : protected _Vector_base<_Tp, _Alloc>
           ^~~~~~
collapse.cpp:43:20: error: expected primary-expression before '>' token
 void solve(vector<Q> qr) {
                    ^
collapse.cpp:43:22: error: 'qr' was not declared in this scope
 void solve(vector<Q> qr) {
                      ^~
collapse.cpp:128:1: error: 'vector' does not name a type
 vector<int> simulateCollapse(
 ^~~~~~