oj.uz

Submission #603524

# Submission time Handle Problem Language Result Execution time Memory
603524 2022-07-24T07:48:45 Z 이동현(#8430) Collapse (JOI18_collapse) C++17
30 / 100
 245 ms 34612 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 << ' ' << (int)bk.size() << 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){
		if(line[i][0] == s && line[i][1] == e){
			gr.unite(line[i][2], line[i][3]);
		}
		else{
			if(line[i][0] <= m){
				lline.push_back({line[i][0], min(m, line[i][1]), line[i][2], line[i][3]});
			}
			if(line[i][1] > m){
				rline.push_back({max(m + 1, line[i][0]), 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);
	}
	grcnt += ((int)bk.size() - bkn) / 2;
	while((int)bk.size() > bkn){
		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
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 3028 KB Output is correct
2 Correct 22 ms 3028 KB Output is correct
3 Correct 104 ms 12600 KB Output is correct
4 Correct 21 ms 3040 KB Output is correct
5 Correct 147 ms 13740 KB Output is correct
6 Correct 39 ms 4104 KB Output is correct
7 Correct 187 ms 30356 KB Output is correct
8 Correct 161 ms 15272 KB Output is correct
9 Correct 26 ms 3040 KB Output is correct
10 Correct 31 ms 3048 KB Output is correct
11 Correct 27 ms 3436 KB Output is correct
12 Correct 177 ms 17676 KB Output is correct
13 Correct 245 ms 25500 KB Output is correct
14 Correct 230 ms 34612 KB Output is correct
15 Correct 223 ms 33220 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 3028 KB Output is correct
2 Incorrect 32 ms 3036 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 -