제출 #102099

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
102099		gs14004	Collapse (JOI18_collapse)	C++17	100 / 100	3009 ms	32952 KiB

collapse

#include <bits/stdc++.h>
using namespace std;
using pi = pair<int, int>;
const int MAXN = 100050;

struct disj{
	int pa[MAXN], rk[MAXN];
	void init(int n){ iota(pa, pa + n, 0); fill(rk, rk + n, 0); }
	int find(int x){
		return pa[x] == x ? x : find(pa[x]);
	}
	bool uni(int p, int q){
		p = find(p);
		q = find(q);
		if(p == q) return 0;
		if(rk[p] < rk[q]) swap(p, q);
		pa[q] = p;
		if(rk[p] == rk[q]) rk[p]++;
		return 1;
	}
	bool uni(int p, int q, vector<pi> &r){
		p = find(p);
		q = find(q);
		if(p == q) return 0;
		if(rk[p] < rk[q]) swap(p, q);
		pa[q] = p;
		r.push_back(pi(1, q));
		if(rk[p] == rk[q]){
			rk[p]++;
			r.push_back(pi(2, p));
		}
		return 1;
	}
	void revert(vector<pi> &r){
		for(int i=(int)r.size()-1; i>=0; i--){
			if(r[i].first == 2) rk[r[i].second]--;
			else pa[r[i].second] = r[i].second;
		}
		r.clear();
	}
}disj;

struct edg{
	int s, e, x;
	bool operator<(const edg &e)const{
		return x < e.x;
	}
}E[MAXN];

struct bit{
	int tree[MAXN];
	void clear(){ memset(tree, 0, sizeof(tree)); }
	void add(int x, int v){
		x++;
		while(x < MAXN){
			tree[x] += v;
			x += x & -x;
		}
	}
	int query(int x){
		x++;
		int ret= 0;
		while(x){
			ret += tree[x];
			x -= x & -x;
		}
		return ret;
	}
}bit;

vector<pi> query[MAXN];
int ans[MAXN];
pi qry[MAXN];
int chk[MAXN];

void solve(int s, int e, vector<int> active_edges){
	if(s == e){
		E[qry[s].first].x = qry[s].second; 
		vector<int> nxt_active_edges = active_edges;
		nxt_active_edges.push_back(qry[s].first);
		sort(nxt_active_edges.begin(), nxt_active_edges.end(), [&](const int &a, const int &b){
			return E[a].x < E[b].x;
		});
		vector<pi> tmp;
		vector<int> sex;
		for(auto &i : nxt_active_edges){
			if(disj.uni(E[i].s, E[i].e, tmp)){
				sex.push_back(E[i].x);
		//		printf("MST add %d\n", i);
				bit.add(E[i].x, 1);
			}
		}
		for(auto &i : query[s]){
			ans[i.second] += bit.query(i.first);
		}
		disj.revert(tmp);
	//	printf("state of query %d\n", s);
		for(auto &i : sex) bit.add(i, -1);
		return;
	}
	int m = (s+e)/2;
	/*** CONTRACTION 1 ***/
	{
		vector<int> nxt_active_edges = active_edges;
		for(int i=m+1; i<=e; i++){
			chk[qry[i].first]--;
			if(chk[qry[i].first] == 0) nxt_active_edges.push_back(qry[i].first);
		}
		sort(nxt_active_edges.begin(), nxt_active_edges.end(), [&](const int &a, const int &b){
			return E[a].x < E[b].x;
		});
		vector<int> maybe, must, cand;
		{
			vector<pi> tmp;
			for(auto &i : nxt_active_edges){
				if(disj.uni(E[i].s, E[i].e, tmp)) maybe.push_back(i);
			}
			disj.revert(tmp);
		}
		{
			vector<pi> tmp;
			for(int i=s; i<=m; i++) disj.uni(E[qry[i].first].s, E[qry[i].first].e, tmp);
			for(auto &i : maybe){
				if(disj.uni(E[i].s, E[i].e, tmp)) must.push_back(i);
				else cand.push_back(i);
			}
			disj.revert(tmp);
		}
		vector<pi> tmp;
		vector<int> sex;
		for(auto &i : must){
	//		printf("MST add %d\n", i);
			disj.uni(E[i].s, E[i].e, tmp);
			bit.add(E[i].x, 1);
			sex.push_back(E[i].x);
		}
		solve(s, m, cand);
		disj.revert(tmp);
		for(int i=m+1; i<=e; i++){
			chk[qry[i].first]++;
		}
		for(auto &i : sex) bit.add(i, -1);
	}
	/*** CONTRACTION 2 ***/
	{
		vector<int> nxt_active_edges = active_edges;
		for(int i=s; i<=m; i++){
			chk[qry[i].first]--;
			if(chk[qry[i].first] == 0) nxt_active_edges.push_back(qry[i].first);
		}
		sort(nxt_active_edges.begin(), nxt_active_edges.end(), [&](const int &a, const int &b){
			return E[a].x < E[b].x;
		});
		vector<int> maybe, must, cand;
		{
			vector<pi> tmp;
			for(auto &i : nxt_active_edges){
				if(disj.uni(E[i].s, E[i].e, tmp)) maybe.push_back(i);
			}
			disj.revert(tmp);
		}
		{
			vector<pi> tmp;
			for(int i=m+1; i<=e; i++) disj.uni(E[qry[i].first].s, E[qry[i].first].e, tmp);
			for(auto &i : maybe){
				if(disj.uni(E[i].s, E[i].e, tmp)) must.push_back(i);
				else cand.push_back(i);
			}
			disj.revert(tmp);
		}
		vector<pi> tmp;
		vector<int> sex;
		for(auto &i : must){
	//		printf("MST add %d\n", i);
			disj.uni(E[i].s, E[i].e, tmp);
			bit.add(E[i].x, 1);
			sex.push_back(E[i].x);
		}
		solve(m+1, e, cand);
		disj.revert(tmp);
		for(int i=s; i<=m; i++){
			chk[qry[i].first]++;
		}
		for(auto &i : sex) bit.add(i, -1);
	}
}

void solve_dmst(int Q, int VN, int EN){
	disj.init(VN);
	vector<int> v;
	memset(chk, 0, sizeof(chk));
	for(int i=0; i<Q; i++) chk[qry[i].first]++;
	for(int i=0; i<EN; i++){
		if(chk[i] == 0) v.push_back(i);
	}
	solve(0, Q-1, v);
}

std::vector<int> simulateCollapse(int N, vector<int> T, vector<int> X, vector<int> Y, vector<int> W, vector<int> P){
	int Q = W.size();
	int C = T.size();
	for(int i=0; i<Q; i++){
		query[W[i]].push_back(pi(P[i], i)); // count edges with weight leq than
	}
	int cnt = 0;
	map<pi, int> mp;
	for(int i=0; i<C; i++){
		if(T[i] == 0){
			E[cnt++] = (edg){X[i], Y[i], N + 3};
			mp[pi(X[i], Y[i])] = mp[pi(Y[i], X[i])] = cnt - 1;
			qry[i] = pi(cnt - 1, max(X[i], Y[i]));
		}
		else{
			qry[i] = pi(mp[pi(X[i], Y[i])], N + 3);
		}
	}
	solve_dmst(C, N, cnt);
	for(int i=0; i<C; i++){
		for(auto &j : query[i]){
			j.first = N - 2 - j.first;
		}
	}
	for(int i=0; i<cnt; i++) E[i].x = N + 3;
	for(int i=0; i<C; i++){
		if(T[i] == 0){
			qry[i].second = N - 1 - min(E[qry[i].first].s, E[qry[i].first].e);
		}
	}
	solve_dmst(C, N, cnt);
	vector<int> ansr(Q);
	for(int i=0; i<Q; i++) ansr[i] = N - ans[i];
	return ansr;
}

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