제출 #1150544

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1150544		brover29	Collapse (JOI18_collapse)	C++20	5 / 100	15092 ms	9076 KiB

collapse

#include "collapse.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N=1e5+29;
set<ll>g[N];
ll x,used[N];
void dfs(ll v){
	used[v]=1;
	for(ll to:g[v]){
		if(used[to]||(v<=x&&x<to)||(to<=x&&x<v))continue;
		dfs(to);
	}
}
vector<int> simulateCollapse(int n,vector<int> T,vector<int> X,vector<int> Y,vector<int> W,vector<int> P) {
	vector<int>ans;
	for(ll i=0;i<P.size();i++){
		x=P[i];
		ll t=W[i];
		for(ll i=0;i<n;i++){
			used[i]=0;
			g[i].clear();
		}
		for(ll i=0;i<=t;i++){
			ll v=X[i];
			ll u=Y[i];
			if(!T[i]){
				g[v].insert(u);
				g[u].insert(v);
			}else{
				g[v].erase(u);
				g[u].erase(v);
			}
		}
		ll cnt=0;
		for(ll i=0;i<n;i++){
			if(!used[i])dfs(i),cnt++;
		}
		ans.push_back(cnt);
	}
	return ans;
}

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