oj.uz

답안 #586775

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
586775 2022-06-30T16:59:06 Z nots0fast Stranded Far From Home (BOI22_island) C++17
0 / 100
 232 ms 105436 KB 
#include <bits/stdc++.h>
using namespace std;
#define mp(a,b) make_pair(a,b)
#define mt make_tuple
#define ff first
#define setp setprecision(12)<<fixed
#define ss second
#define fori(v) for(int i=0; i<v; i++)
#define forj(v) for(int j=0; j<v; j++)
#define fork(v) for(int k=0; k<v; k++)
#define forl(v) for(int l=0; l<v; l++)
#define fort(v) for(int t=0; t<v; t++)
#define forz(v) for(int z=0; z<v; z++)
#define ll long long
#define lll __int128
#define ld long double
#define pb(a) push_back(a)
// #define cout out
// #define cin in
ll inf = pow(10,18);
ll modulo = 1000000007;
double eps = 1e-10;
ifstream in;
ofstream out;

#define MAX 200'200


ll arr[MAX];

namespace dsu{
	int aid[MAX];
	vector<int> dsu[MAX];
	vector<ll> good[MAX];
	priority_queue<pair<int, int> , vector<pair<int, int> > , greater<pair<int, int> > > edg[MAX];
	ll s[MAX];
	void ini(int n){
		fori(n)
			aid[i] = i, dsu[i].clear(), dsu[i].push_back(i), good[i].pb(i), s[i] = arr[i];
	}
	ll join(int a,int b){  //	1 - if joined, 0 - if they were already joined 
		int aid1 = aid[a], aid2 = aid[b];
		if(aid1==aid2)
			return -1;
		
		if(dsu[aid2].size() > dsu[aid1].size())
			swap(aid1,aid2);
		
		{
			if(good[aid1].size() < good[aid2].size()){
				swap(good[aid1], good[aid2]);
			}
			for(auto& el : good[aid2]){
				good[aid1].pb(el);
			}
		}
		
		{
			if(edg[aid1].size() < edg[aid2].size()){
				swap(edg[aid1], edg[aid2]);
			}
			while(!edg[aid2].empty()){
				auto tp = edg[aid2].top();
				auto hd = tp.ss;
				if(aid[hd] != aid1 && aid[hd]!=aid2){
					edg[aid1].push(tp);
				}
				edg[aid2].pop();
			}
		}
		
		
		for(auto hd : dsu[aid2]){
			aid[hd] = aid1;
			dsu[aid1].push_back(hd);
		}
		dsu[aid2].clear();
		good[aid2].clear();
		s[aid1]+=s[aid2];
		
		return aid1;
	}
};

using namespace dsu;

void deal(){
	ll n, m;
	cin>>n>>m;
	
	fori(n){
		cin>>arr[i];
	}
	ini(n);
	
	fori(m){
		ll ai, bi;
		cin>>ai>>bi;
		--ai, --bi;
		edg[ai].push(mp(arr[bi], bi));
		edg[bi].push(mp(arr[ai], ai));
	}
	
	
	set<pair<ll, ll> > all; // components and their sizes
	fori(n){
		all.insert(mp(arr[i], i));
	}
	
	while((ll)all.size() > 1){
		auto it = all.begin();
		ll hd = (*it).ss;
		all.erase(all.begin());
		
		
		while(1){
			assert(!edg[hd].empty());
			auto it = edg[hd].top();
			edg[hd].pop();
			ll wh = it.ss;
			if(aid[wh] == hd){
				continue;
			}
			else{
				if(s[hd] >= arr[wh]){
					ll hr = aid[wh];
					assert(all.find(mp(s[hr], hr) )!=all.end());
					all.erase(mp(s[hr], hr));
					ll cr = join(hd, hr);
					all.insert(mp(s[cr], cr));
				}
				else{
					good[hd].clear();
				}
				break;
			}
		}
		
	}
	
	ll cr = aid[0];
	vector<bool> ans(n, 0);
	for(auto& el : good[cr]){
		ans[el] = 1;
	}
	fori(n){
		cout<<ans[i];
	}
}

int main(){
	cin.tie(0);
	ios_base::sync_with_stdio(0);
	deal();
}

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 15956 KB Output is correct
2 Runtime error 27 ms 32244 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 21 ms 32300 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 15924 KB Output is correct
2 Runtime error 230 ms 103148 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 15972 KB Output is correct
2 Runtime error 232 ms 105436 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 15956 KB Output is correct
2 Runtime error 27 ms 32244 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -