Submission #126663

#	Time	Username	Problem	Language	Result	Execution time	Memory
126663		E869120	Collapse (JOI18_collapse)	C++14	0 / 100	15091 ms	308468 KiB

collapse

#include "collapse.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;

const int MAX_N = (1 << 17);
const int MAX_UF = 181;
const int BACKET = 1209;

class SuperiorRankUnionFind {
public:
	int query = 0, numedge = 0;
	vector<int> par, ranks;
	vector<pair<int, int>> G_par, G_ranks;

	void init(int sz) {
		query = 0; numedge = 0;
		par.resize(sz, -1);
		ranks.resize(sz, -1);
		G_par.resize(MAX_N, make_pair(-1, -1));
		G_ranks.resize(MAX_N, make_pair(-1, -1));
	}
	int root(int pos) {
		while (par[pos] != -1) {
			pos = par[pos];
		}
		return pos;
	}
	void unite(int u, int v) {
		query++;
		u = root(u); v = root(v);
		if (u == v) return;

		if (ranks[u] > ranks[v]) swap(u, v);

		G_par[query] = make_pair(u, par[u]);
		par[u] = v;
		G_ranks[query] = make_pair(u, ranks[u]);
		ranks[u] = v;
		numedge++;
	}
	void reversi() {
		if (G_par[query] != make_pair(-1, -1)) {
			pair<int, int> E = G_par[query];
			par[E.first] = E.second;
		}
		if (G_ranks[query] != make_pair(-1, -1)) {
			pair<int, int> E = G_ranks[query];
			ranks[E.first] = E.second;
		}
		if (G_par[query] != make_pair(-1, -1)) numedge--;
		G_par[query] = make_pair(-1, -1);
		G_ranks[query] = make_pair(-1, -1);
		query--;
	}
};

int SIZE_ = 1;
int N, C, Q, T[MAX_N], X[MAX_N], Y[MAX_N], W[MAX_N], P[MAX_N], ans[MAX_N];
vector<pair<int, int>> Question[MAX_N];
vector<pair<int, int>> G[MAX_N * 2];
map<pair<int, int>, int> Map;

SuperiorRankUnionFind UF[209]; int cnts, el[209], er[209], deg[MAX_N];
vector<tuple<int, int, int, int>> PossibleEdge[209];

void add_(int l, int r, pair<int, int>x, int a, int b, int u) {
	if (l <= a && b <= r) {
		G[u].push_back(x);
		return;
	}
	if (r <= a || b <= l) return;
	add_(l, r, x, a, (a + b) >> 1, u * 2);
	add_(l, r, x, (a + b) >> 1, b, u * 2 + 1);
}

void add_edge(int l, int r, pair<int, int>x) {
	for (int i = 1; i <= cnts; i++) {
		if ((el[i] <= x.first && x.first <= er[i]) || (el[i] <= x.second && x.second <= er[i])) {
			PossibleEdge[i].push_back(make_tuple(x.first, x.second, l, r));
		}
	}
	add_(l, r, x, 0, SIZE_, 1);
}

void dfs(int dl, int dr, int u) {
	// 辺の追加
	for (int i = 1; i <= cnts; i++) {
		for (pair<int, int> edge : G[u]) {
			if (edge.second <= el[i] || er[i] < edge.first) UF[i].unite(edge.first, edge.second);
		}
	}

	// 探索続行 (u < SIZE)、判定 (u >= SIZE)
	if (u < SIZE_) {
		dfs(dl, (dl + dr) >> 1, u * 2);
		dfs((dl + dr) >> 1, dr, u * 2 + 1);
	}

	else {
		for (pair<int, int> que : Question[u - SIZE_]) {
			int p = que.first, id = -1;
			for (int i = 1; i <= cnts; i++) {
				if (el[i] <= p && p <= er[i]) id = i;
			}
			int cntv = 0;
			for (int i = 0; i < PossibleEdge[id].size(); i++) {
				tuple<int, int, int, int> H = PossibleEdge[id][i];
				if (get<2>(H) <= u - SIZE_ && u - SIZE_ <= get<3>(H) && (get<1>(H) <= p || p < get<0>(H))) {
					UF[id].unite(get<0>(H), get<1>(H)); cntv++;
				}
			}
			ans[que.second] = N - UF[id].numedge;
			for (int i = 1; i <= cntv; i++) UF[id].reversi();
		}
	}

	// 辺の削除
	for (int i = 1; i <= cnts; i++) {
		int cntv = 0;
		for (pair<int, int> edge : G[u]) {
			if (edge.second < el[i] || er[i] < edge.first) cntv++;
		}
		for (int j = 0; j < cntv; j++) UF[i].reversi();
	}
}

vector<int> solve() {
	// Step 1 : 幅を決める
	for (int i = 1; i <= C; i++) { deg[X[i]]++; deg[Y[i]]++; }

	int sum1 = 0, id = 1;
	for (int i = 1; i <= N; i++) {
		sum1 += deg[i];
		if (sum1 + deg[i + 1] > BACKET || i == N) {
			cnts++;
			el[cnts] = id;
			er[cnts] = i;
			sum1 = 0; id = i + 1;
		}
	}

	// Step 2 : 前準備
	while (SIZE_ <= C) SIZE_ *= 2;
	for (int i = 1; i <= C; i++) {
		if (T[i] == 0) {
			Map[make_pair(X[i], Y[i])] = i;
		}
		if (T[i] == 1) {
			int S = Map[make_pair(X[i], Y[i])];
			add_edge(S, i, make_pair(X[i], Y[i]));
			Map[make_pair(X[i], Y[i])] = 0;
		}
	}
	for (int i = 1; i <= C; i++) {
		if (Map[make_pair(X[i], Y[i])] != 0) {
			int S = Map[make_pair(X[i], Y[i])];
			add_edge(S, C + 1, make_pair(X[i], Y[i]));
			Map[make_pair(X[i], Y[i])] = 0;
		}
	}

	// Step 3 : 質問の設定
	for (int i = 1; i <= Q; i++) {
		Question[W[i]].push_back(make_pair(P[i], i));
	}
	for (int i = 1; i <= cnts; i++) UF[i].init(N + 2);

	// Step 4 : 探索
	dfs(0, SIZE_, 1);

	// Step 5 : 最終決定
	vector<int>FinalAns;
	for (int i = 1; i <= Q; i++) FinalAns.push_back(ans[i]);
	return FinalAns;
}

vector<int> simulateCollapse(int N1, vector<int>T1, vector<int>X1, vector<int>Y1, vector<int>W1, vector<int>P1) {
	N = N1; C = T1.size(); Q = W1.size();
	for (int i = 1; i <= C; i++) T[i] = T1[i - 1];
	for (int i = 1; i <= C; i++) { X[i] = X1[i - 1]; X[i]++; }
	for (int i = 1; i <= C; i++) { Y[i] = Y1[i - 1]; Y[i]++; }
	for (int i = 1; i <= Q; i++) { W[i] = W1[i - 1]; W[i]++; }
	for (int i = 1; i <= Q; i++) { P[i] = P1[i - 1]; P[i]++; }
	for (int i = 1; i <= C; i++) { if (X[i] > Y[i]) swap(X[i], Y[i]); }

	return solve();
}

Compilation message (stderr)

collapse.cpp: In function 'void dfs(int, int, int)':
collapse.cpp:109:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int i = 0; i < PossibleEdge[id].size(); i++) {
                    ~~^~~~~~~~~~~~~~~~~~~~~~~~~

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