Submission #1215445

#	Time	Username	Problem	Language	Result	Execution time	Memory
1215445		JooDdae	Collapse (JOI18_collapse)	C++20	30 / 100	1594 ms	18324 KiB

collapse

 #include "collapse.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

// TODO : delete

const int sq = 350;

struct UnionFind {
	vector<int> P, S;
	int N;
	vector<array<int, 2>> rb;

	UnionFind(int N): N(N), P(N), S(N, 1) { iota(P.begin(), P.end(), 0); }

	int find(int x) { return x == P[x] ? x : find(P[x]); }
	void merge(int x, int y) {
		if((x = find(x)) == (y = find(y))) return;
		if(S[x] > S[y]) swap(x, y);
		S[y] += S[x], P[x] = P[y];
		rb.push_back({x, y});
	}

	void rollBack(int k) {
		while(rb.size() > k) {
			auto [x, y] = rb.back(); rb.pop_back();
			S[y] -= S[x], P[x] = x;
		}
	}
};

void solve(int N, int M, vector<int> &T, vector<int> &X, vector<int> &Y, vector<int> &W, vector<int> &P, vector<int> &re) {
	int C = (X.size()-1)/sq+1;
	vector<vector<array<int, 3>>> Q(C);
	for(int i=0;i<M;i++) Q[W[i]/sq].push_back({P[i], W[i], i});
	set<int> s[N];
	for(int i=0, r=0;i<C;i++) {
		while(r < i*sq) {
			int L = min(X[r], Y[r]), R = max(X[r], Y[r]);
			if(T[r]) s[R].erase(L);
			else s[R].insert(L);
			r++;
		}

		sort(Q[i].begin(), Q[i].end());
		UnionFind uf(N);
		
		for(int j=0, k=0;j<N-1;j++) {
			for(auto L : s[j]) uf.merge(L, j);

			while(k < Q[i].size() && Q[i][k][0] == j) {
				auto [P, W, id] = Q[i][k++];
				int rev = uf.rb.size();

				for(int u=r;u<=W;u++) if(max(X[u], Y[u]) <= P) uf.merge(X[u], Y[u]);
				re[id] -= uf.rb.size();

				uf.rollBack(rev);
			}
		}
	}
}

vector<int> simulateCollapse(int N, vector<int> T, vector<int> X, vector<int> Y, vector<int> W, vector<int> P) {
	int M = W.size();
	vector<int> re(M, N);

	solve(N, M, T, X, Y, W, P, re);
	for(int i=0;i<X.size();i++) X[i] = N-X[i]-1, Y[i] = N-Y[i]-1;
	for(int i=0;i<M;i++) P[i] = N-P[i]-2;
	solve(N, M, T, X, Y, W, P, re);

	return re;
}

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