제출 #380909

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
380909		qwerty234	Collapse (JOI18_collapse)	C++14	100 / 100	7474 ms	31268 KiB

collapse

#include <bits/stdc++.h>
#include "collapse.h"
#define pb push_back
#define fi first
#define se second
using namespace std;

const int blocksz = 300;

struct query {
	int plan_day, collapse_town, id;
	query(int x, int y, int z) {plan_day = x; collapse_town = y; id = z;}
};
bool cmpquery(query A, query B) {return A.plan_day < B.plan_day;}

struct operation {
	int u, v, sz_u, sz_v;
	operation(int x, int y, int z, int d) {u = x; v = y; sz_u = z; sz_v = d;}
};
vector <int> sz, p;
vector <operation> op;
int sz_comp;

void make_set(int n) {
	sz.assign(n, 1); p.assign(n, 0); op.clear();
	for (int i = 0; i < n; i++) p[i] = i;
	sz_comp = n;
}

int getp(int u) {
	if (p[u] == u) return u;
	return getp(p[u]);
}

int add(int u, int v) {
	u = getp(u); v = getp(v);
	if (u == v) return 0;
	if (sz[u] > sz[v]) swap(u, v);
	op.pb({u, v, sz[u], sz[v]});
	p[u] = v;
	sz[v] += sz[u];
	sz_comp--;
	return 1;
}

void go_back() {
	operation opp = op[op.size() - 1];
	int u = opp.u, v = opp.v, sz_u = opp.sz_u, sz_v = opp.sz_v;
	p[u] = u; p[v] = v; sz[u] = sz_u; sz[v] = sz_v;
	sz_comp++;
	op.pop_back();
}

vector <int> simulateCollapse(int n, vector <int> t, vector <int> x, vector <int> y, vector <int> w, vector <int> p) {
	int c = t.size(), q = w.size(), m = 0;
	// if (n > 5005 || c > 5005 || q > 5005)
	// 	return {};
	vector <query> qu; qu.clear();
	for (int i = 0; i < q; i++) {
		qu.pb({w[i], p[i], i});
	}
	sort(qu.begin(), qu.end(), cmpquery);
	vector <int> refer, state, vis; refer.assign(c, 0);
	vector <pair<int, int>> edges; edges.clear();
	map <pair<int, int>, int> edge_id; edge_id.clear();
	for (int i = 0; i < c; i++) {
		if (x[i] > y[i]) swap(x[i], y[i]);
		if (!edge_id.count({x[i], y[i]})) {
			edge_id[{x[i], y[i]}] = m++; edges.pb({x[i], y[i]});
		}
		refer[i] = edge_id[{x[i], y[i]}];
	}
	vector <vector<int>> min_v, max_v, qus_v; min_v.assign(n, {}); max_v.assign(n, {}); qus_v.assign(n, {});
	vector <int> ans; ans.assign(q, 0);
	int curblock = 0;
	while (true) {
		int l = curblock * blocksz, r = min(l + blocksz - 1, q - 1);
		vis.assign(m, 0); state.assign(m, 0);
		if (l >= q) break;
		for (int j = 0; j < qu[l].plan_day; j++) state[refer[j]] ^= 1;
		for (int i = 0; i < n; i++) {
			min_v[i].clear(); max_v[i].clear(); qus_v[i].clear();
		}
		for (int i = l; i <= r; i++) {
			qus_v[qu[i].collapse_town].pb(i);
		}
		for (int j = qu[l].plan_day; j <= qu[r].plan_day; j++)
			vis[refer[j]] = 1;
		for (int i = 0; i < m; i++) {
			if (state[i] && !vis[i]) {
				min_v[edges[i].fi].pb(i);
				max_v[edges[i].se].pb(i);
			}
		}
		make_set(n);
		for (int i = 0; i <= n - 2; i++) {
			for (int id : max_v[i])
				add(edges[id].fi, edges[id].se);
			for (int id : qus_v[i]) {
				int cnt_op = 0;
				for (int j = qu[l].plan_day; j <= qu[id].plan_day; j++) state[refer[j]] ^= 1;
				for (int j = qu[l].plan_day; j <= qu[r].plan_day; j++) {
					if (state[refer[j]] && edges[refer[j]].se <= i)
						cnt_op += add(edges[refer[j]].fi, edges[refer[j]].se);
				}
				for (int j = qu[l].plan_day; j <= qu[id].plan_day; j++) state[refer[j]] ^= 1;
				ans[qu[id].id] += sz_comp - (n - i - 1);
				while (cnt_op--) go_back();
			}
		}
		make_set(n);
		for (int i = n - 1; i >= 1; i--) {
			for (int id : min_v[i])
				add(edges[id].fi, edges[id].se);
			for (int id : qus_v[i - 1]) {
				int cnt_op = 0;
				for (int j = qu[l].plan_day; j <= qu[id].plan_day; j++) state[refer[j]] ^= 1;
				for (int j = qu[l].plan_day; j <= qu[r].plan_day; j++) {
					if (state[refer[j]] && i <= edges[refer[j]].fi)
						cnt_op += add(edges[refer[j]].fi, edges[refer[j]].se);
				}
				for (int j = qu[l].plan_day; j <= qu[id].plan_day; j++) state[refer[j]] ^= 1;
				ans[qu[id].id] += sz_comp - i;
				while (cnt_op--) go_back();
			}
		}
		curblock++;
	}
	return ans;
}

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