Submission #102201

#	Time	Username	Problem	Language	Result	Execution time	Memory
102201		Minnakhmetov	Collapse (JOI18_collapse)	C++14	100 / 100	4342 ms	20788 KiB

collapse

#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <cstring>
#include <unordered_map>
#include <unordered_set>

#include "collapse.h"
using namespace std;

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);
	fill(usede, usede + 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 = s.size() - 1, j = 0, r = 0; i >= 0; 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]);

		int num;
		if (!mp_e.count({ X[i], Y[i] })) {
			num = edges.size();
			edges.push_back({ X[i], Y[i], num });
			mp_e[{X[i], Y[i]}] = num;
			se1.push_back({ X[i], Y[i], num });
			se2.push_back({ Y[i], X[i], num });
		}
		else {
			num = mp_e[{X[i], Y[i]}];
		}
		
		v.push_back({ i, 1, num });
	}

	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 (stderr)

collapse.cpp: In function 'void solve(std::vector<Q>)':
collapse.cpp:119:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0, j = 0, r = 0; i < s.size(); i++) {
                                ~~^~~~~~~~~~
collapse.cpp:120:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while (j < se1.size() && se1[j].x <= s[i].x) {
          ~~^~~~~~~~~~~~
collapse.cpp:137:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while (j < se2.size() && se2[j].x > s[i].x) {
          ~~^~~~~~~~~~~~
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:211:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < v.size(); i++) {
                  ~~^~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 30 / 30
• Subtask 3: 30 / 30
• Subtask 4: 35 / 35