제출 #60849

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
60849		egorlifar	Collapse (JOI18_collapse)	C++17	100 / 100	7182 ms	107988 KiB

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>
#include <bits/stdc++.h> 

     
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;
}

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