oj.uz

Submission #603498

# Submission time Handle Problem Language Result Execution time Memory
603498 2022-07-24T07:38:35 Z 이동현(#8430) Collapse (JOI18_collapse) C++17
0 / 100
 42 ms 3044 KB 
#include "collapse.h"
#include <bits/stdc++.h>
using namespace std;

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

int grcnt;
vector<vector<int>> bk;
struct Dsu{
	int n;
	vector<int> pr, rk;
	Dsu(){}
	Dsu(int n):n(n + 4){
		pr.resize(n), rk.resize(n);
		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;
	}
}gr(NS);

int ans[NS];

void dnc(int s, int e, vector<vector<int>> line){
	//cout << s << ' ' << e << endl;
	//for(auto&i:line){
	//	cout << i[0] << ' ' << i[1] << ' ' << i[2] << ' ' << i[3] << endl;
	//}
	if(s > e) return;
	int bkn = (int)bk.size();
	vector<vector<int>> lline, rline;
	int m = s + e >> 1;
	for(int i = 0; i < (int)line.size(); ++i){
		assert(line[i][0] >= s && line[i][1] <= e);
		if(line[i][0] == s && line[i][1] == e){
			gr.unite(line[i][2], line[i][3]);
		}
		if(line[i][0] <= m){
			lline.push_back({line[i][0], m, line[i][2], line[i][3]});
		}
		if(line[i][1] > m){
			rline.push_back({m + 1, line[i][1], line[i][2], line[i][3]});
		}
	}
	if(s == e){
		ans[s] = grcnt;
	}
	else{
		dnc(s, m, lline);
		dnc(m + 1, e, rline);
	}
	while((int)bk.size() > bkn){
		++grcnt;
		if(bk.back()[0] == 0){
			gr.pr[bk.back()[1]] = bk.back()[2];
		}
		else{
			gr.rk[bk.back()[1]] = bk.back()[2];
		}
		bk.pop_back();
	}
}

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();
	grcnt = n;
	vector<int> del(m);
	for(int i = 0; i < m; ++i){
		if(X[i] > Y[i]){
			swap(X[i], Y[i]);
		}
		if(X[i] <= P[0] && Y[i] > P[0]){
			del[i] = 1;
		}
	}
	vector<int> nt, nx, ny;
	for(int i = 0; i < m; ++i){
		if(del[i]) continue;
		nt.push_back(T[i]), nx.push_back(X[i]), ny.push_back(Y[i]);
	}
	swap(T, nt), swap(X, nx), swap(Y, ny);
	for(int i = 1; i < m; ++i){
		del[i] += del[i - 1];
	}
	for(int i = 0; i < q; ++i){
		W[i] -= del[W[i]];
	}
	m = (int)T.size();

	vector<int> r(m, -1);
	map<pair<int, int>, int> mp;
	for(int i = m - 1; i >= 0; --i){
		if(T[i] == 1){
			mp[{X[i], Y[i]}] = i;
		}
		else{
			if(mp[{X[i], Y[i]}]){
				r[i] = mp[{X[i], Y[i]}];
			}
		}
	}

	vector<vector<int>> line;
	for(int i = 0; i < m; ++i){
		if(T[i] == 1){
			continue;
		}
		if(r[i] == -1){
			line.push_back({i, m - 1, X[i], Y[i]});
		}
		else{
			line.push_back({i, r[i] - 1, X[i], Y[i]});
		}
	}

	dnc(0, m - 1, line);

	vector<int> rv(q);
	for(int i = 0; i < q; ++i){
		if(W[i] >= 0) rv[i] = ans[W[i]];
		else rv[i] = n;
	}
	return rv;
}

Compilation message

collapse.cpp: In function 'void dnc(int, int, std::vector<std::vector<int> >)':
collapse.cpp:48:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   48 |  int m = s + e >> 1;
      |          ~~^~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1236 KB Output is correct
2 Incorrect 2 ms 1108 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 3032 KB Output is correct
2 Incorrect 30 ms 3036 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 3044 KB Output is correct
2 Incorrect 41 ms 3028 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1236 KB Output is correct
2 Incorrect 2 ms 1108 KB Output isn't correct
3 Halted 0 ms 0 KB -