Submission #1215488

#	Time	Username	Problem	Language	Result	Execution time	Memory
1215488		JooDdae	Collapse (JOI18_collapse)	C++20	35 / 100	15085 ms	16672 KiB

collapse

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

const int sq = 350;

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

	UnionFind(int N): N(N), P(N), S(N, 1), rb(N), sz(0) { 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[sz++] = {x, y};
	}

	void rollBack(int k) {
		while(sz > k) {
			auto [x, y] = rb[--sz];
			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 K = X.size();
	int C = (K-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});
	
	vector<array<int, 3>> V(K);
	for(int i=0;i<K;i++) V[i] = {min(X[i], Y[i]), max(X[i], Y[i]), i};
	sort(V.begin(), V.end());

	vector<array<int, 4>> E;
	for(int i=0;i<K;i++) {
		auto [x, y, t] = V[i];
		int j = i;
		while(j+1 < K && V[j+1][0] == x && V[j+1][1] == y) j++;
		for(int k=i;k<=j;k+=2) E.push_back({x, y, V[k][2], k == j ? K : V[k+1][2]-1});
		i = j;
	}

	for(int i=0;i<C;i++) {
		int L = i*sq, R = min(L+sq-1, K-1);
		vector<vector<int>> s(N);
		vector<array<int, 4>> sp;
		
		for(auto [x, y, l, r] : E) {
			if(l <= L && R <= r) s[y].push_back(x);
			else if(L <= r || l <= R) sp.push_back({x, y, 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.sz;

				for(auto [x, y, l, r] : sp) if(l <= W && W <= r && max(x, y) <= P) uf.merge(x, y);
				re[id] -= uf.sz;

				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: 5 / 5
• Subtask 2: 0 / 30
• Subtask 3: 30 / 30
• Subtask 4: 0 / 35