Submission #1054490

#	Time	Username	Problem	Language	Result	Execution time	Memory
1054490		aymanrs	Collapse (JOI18_collapse)	C++17	5 / 100	15032 ms	9840 KiB

collapse

#include "collapse.h"
#include <bits/stdc++.h>
using namespace std;
void dfs(int n, set<int> g[], bool v[], int p){
	v[n]=true;
	for(int j : g[n]){
		if(v[j]) continue;
		if(min(n,j) <= p && max(n,j) > p) continue;
		dfs(j, g, v, p);
	}
}
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 q = W.size();
	vector<int> ans(q);
	int o[q];
	for(int i = 0;i < q;i++) o[i]=i;
	sort(o, o+q, [&W](int a, int b){return W[a]<W[b];});
	int tim = 0;
	set<int> g[N];
	bool v[N];
	for(int _ = 0;_ < q;_++){
		int qi = o[_];
		int t = W[qi];
		while(tim <= t){
			if(T[tim]){
				g[X[tim]].erase(Y[tim]);
				g[Y[tim]].erase(X[tim]);
			} else {
				g[X[tim]].insert(Y[tim]);
				g[Y[tim]].insert(X[tim]);
			}
			tim++;
		}
		ans[qi] = 0;
		fill(v,v+N,false);
		for(int i = 0;i < N;i++) {
			if(!v[i]){
				ans[qi]++;
				dfs(i, g, v, P[qi]);
			}
		}
	}
	return ans;
}

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