oj.uz

Submission #603661

# Submission time Handle Problem Language Result Execution time Memory
603661 2022-07-24T09:25:53 Z 이동현(#8430) Collapse (JOI18_collapse) C++17
0 / 100
 179 ms 7756 KB 
#include "collapse.h"
#include <bits/stdc++.h>
using namespace std;

const int NS = (int)1e5 + 4;

vector<vector<int>> bk;
struct Dsu{
	int n, grcnt;
	vector<int> pr, rk;
	Dsu(){}
	Dsu(int n, int nn):n(n + 4){
		pr.resize(n), rk.resize(n);
		grcnt = 0;
		for(int i = 0; i < n; ++i){
			pr[i] = i;
			rk[i] = 1;
		}
	}
	int fd(int x){
		return (x == pr[x] ? x : fd(pr[x]));
	}
	bool unite(int x, int y){
		x = fd(x), y = fd(y);
		if(x == y) return false;
		if(rk[x] > rk[y]){
			swap(x, y);
		}
		bk.push_back({1, y, rk[y]});
		bk.push_back({0, x, pr[x]});
		++grcnt;
		rk[y] += rk[x];
		pr[x] = y;
		return true;
	}
};

std::vector<int> simulateCollapse(
	int N,
	std::vector<int> T,
	std::vector<int> X,
	std::vector<int> Y,
	std::vector<int> W,
	std::vector<int> P
) {
	int n = N, m = (int)T.size(), q = (int)W.size();
	int B = (int)1e9 + 4;

	vector<Dsu> gr(n / B + 4);
	for(int i = 0; i < (int)gr.size(); ++i){
		gr[i] = Dsu(n + 1, n);
	}
	vector<vector<int>> qsrt;
	for(int i = 0; i < q; ++i){
		qsrt.push_back({P[i], W[i], i});
	}
	sort(qsrt.begin(), qsrt.end());
	vector<vector<int>> msrt;
	for(int i = 0; i < m; ++i){
		msrt.push_back({X[i], Y[i], i});
	}
	sort(msrt.begin(), msrt.end(), [&](vector<int>&x, vector<int>&y){return x[1] < y[1];});

	vector<int> ans(q);
	int j = 0;
	vector<int> chk(m);
	auto doit = [&](int&j, int dir = 0){
		bk.clear();
		int pos = qsrt[j][1] / B - 1, lst = qsrt[j][1] / B * B - 1;
		if(pos == -1) pos = (int)gr.size() - 1;
		while(lst < qsrt[j][1]){
			++lst;
			if(chk[lst]){
				gr[pos].unite(X[lst], Y[lst]);
			}
		}
		if(!dir) ans[qsrt[j][2]] += qsrt[j][0] + 1 - gr[pos].grcnt;
		else ans[qsrt[j][2]] += n - qsrt[j][0] - 1 - gr[pos].grcnt;
		++j;
		gr[pos].grcnt -= (int)bk.size() / 2;
		while((int)bk.size()){
			if(bk.back()[0] == 0){
				gr[pos].pr[bk.back()[1]] = bk.back()[2];
			}
			else{
				gr[pos].rk[bk.back()[1]] = bk.back()[2];
			}
			bk.pop_back();
		}
	};
	for(int i = 0; i < (int)msrt.size(); ++i){
		while(j < (int)qsrt.size() && qsrt[j][0] < msrt[i][1]){
			doit(j);
		}
		int pos = msrt[i][2] / B;
		while(pos < (int)gr.size() - 1){
			gr[pos].unite(msrt[i][0], msrt[i][1]);
			++pos;
		}
		chk[msrt[i][2]] = 1;
	}
	while(j < (int)qsrt.size()) doit(j);

	chk = vector<int>(m, 0);
	gr = vector<Dsu>(n / B + 4);
	for(int i = 0; i < (int)gr.size(); ++i){
		gr[i] = Dsu(n + 1, n);
	}
	sort(msrt.begin(), msrt.end(), [&](vector<int>&x, vector<int>&y){return x[0] < y[0];});
	reverse(qsrt.begin(), qsrt.end());
	j = 0;
	for(int i = (int)msrt.size() - 1; i >= 0; --i){
		while(j < (int)qsrt.size() && qsrt[j][0] >= msrt[i][0]){
			doit(j, 1);
		}
		int pos = msrt[i][2] / B;
		while(pos < (int)gr.size() - 1){
			gr[pos].unite(msrt[i][0], msrt[i][1]);
			++pos;
		}
		chk[msrt[i][2]] = 1;
	}
	while(j < (int)qsrt.size()) doit(j, 1);
	return ans;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 179 ms 1116 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 49 ms 7648 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 52 ms 7756 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Incorrect 179 ms 1116 KB Output isn't correct
2 Halted 0 ms 0 KB -