Submission #57611

#	Time	Username	Problem	Language	Result	Execution time	Memory
57611		model_code	Collapse (JOI18_collapse)	C++17	100 / 100	7553 ms	30812 KiB

collapse

#include "collapse.h"
#include <utility>
#include <algorithm>
#include <set>
#include <iostream>
#include <memory>

template<typename T> using vector = std::vector<T>;
template<typename T> using set = std::set<T>;
template<typename T, typename S> using pair = std::pair<T, S>;
using std::make_pair;
using Paths = vector<pair<int, int>>;

const int Bucket = 1000;

class UnionFind {
private:
	vector<int> parent;
	vector<int> rank;
	bool need_change;
	vector<int> change;
public:
	UnionFind(int n, bool need_change_ = false) : parent(n), rank(n, 0), need_change(need_change_) {
		for(int i = 0; i < n; i++) parent[i] = i;
	}
	int findParent(int x) {
		if(parent[x] == x) return x;
		return parent[x] = findParent(parent[x]);
	}
	bool unionGroup(int x, int y) {
		int xp = findParent(x);
		int yp = findParent(y);
		if(xp == yp) {
			return false;
		}
		else {
			if(need_change) {
				change.push_back(xp);
				change.push_back(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,
	Paths fixed,
	vector<pair<int, pair<int, std::shared_ptr<Paths>>>> 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, std::shared_ptr<Paths>>>& a, const pair<int, pair<int, std::shared_ptr<Paths>>>& b){ return a.first < b.first; };
	sort(fixed.begin(), fixed.end(), comp_second);
	sort(query.begin(), query.end(), comp_first_only);
	vector<pair<int, int>> ret;
	UnionFind large(n), tmp(n, true);
	int now = 0;
	int count = 0;
	for(auto i : query) {
		while(now < (int)fixed.size() && fixed[now].second <= i.first) {
			if(large.unionGroup(fixed[now].first, fixed[now].second)) count++;
			now++;
		}
		int c = count;
		for(auto j : *i.second.second)
			if(j.second <= i.first && tmp.unionGroup(large.findParent(j.first), large.findParent(j.second))) c++;
		ret.push_back(make_pair(i.second.first, i.first + 1 - c));
		tmp.reset();
	}
	return ret;
}

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

pair<int, int> revPath(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 < (int)W.size(); i++) {
		q.push_back(make_pair(make_pair(W[i], P[i]), i));
	}
	sort(q.begin(), q.end());
	vector<int> ans(q.size(), 0);
	set<pair<int, int>> path;
	int now = 0;
	for(int s = 0; s < (int)T.size(); s += Bucket) {
		int e = std::min(s + Bucket, (int)T.size());
		
		set<pair<int, int>> change;
		for(int i = s; i < e; i++) change.insert(minMaxPair(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);
		}
		
		Paths fixed1, fixed2;
		for(auto i : fixed_) {
			fixed1.push_back(i);
			fixed2.push_back(revPath(N, i));
		}
		
		vector<pair<int, pair<int, std::shared_ptr<Paths>>>> query1, query2;
		for(int i = s; i < e; i++) {
			if(T[i] == 0) {
				path.insert(minMaxPair(X[i], Y[i]));
				np.insert(minMaxPair(X[i], Y[i]));
			}
			else {
				path.erase(minMaxPair(X[i], Y[i]));
				np.erase(minMaxPair(X[i], Y[i]));
			}
			std::shared_ptr<Paths> p1(new Paths), p2(new Paths);
			for(auto j : np) {
				p1->push_back(j);
				p2->push_back(revPath(N, j));
			}
			while(now < (int)q.size() && q[now].first.first == i) {
				query1.push_back(make_pair(q[now].first.second, make_pair(q[now].second, p1)));
				query2.push_back(make_pair(N - 2 - q[now].first.second, make_pair(q[now].second, p2)));
				now++;
			}
		}
		
		for(auto i : solve(N, fixed1, query1)) ans[i.first] += i.second;
		for(auto i : solve(N, fixed2, query2)) ans[i.first] += i.second;
	}
	return ans;
}

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