oj.uz

답안 #586770

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
586770 2022-06-30T16:51:58 Z nots0fast Stranded Far From Home (BOI22_island) C++17
10 / 100
 1000 ms 64220 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){
			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];
					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 10 ms 15896 KB Output is correct
2 Correct 11 ms 15956 KB Output is correct
3 Correct 8 ms 15908 KB Output is correct
4 Execution timed out 1089 ms 16284 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 15956 KB Output is correct
2 Correct 8 ms 15956 KB Output is correct
3 Correct 438 ms 64220 KB Output is correct
4 Correct 288 ms 52376 KB Output is correct
5 Correct 565 ms 60508 KB Output is correct
6 Correct 565 ms 61556 KB Output is correct
7 Correct 567 ms 62476 KB Output is correct
8 Correct 389 ms 54120 KB Output is correct
9 Correct 355 ms 60752 KB Output is correct
10 Correct 165 ms 52968 KB Output is correct
11 Correct 278 ms 52980 KB Output is correct
12 Correct 434 ms 55956 KB Output is correct
13 Correct 338 ms 51328 KB Output is correct
14 Correct 273 ms 51396 KB Output is correct
15 Correct 284 ms 52940 KB Output is correct
16 Correct 190 ms 52472 KB Output is correct

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 15956 KB Output is correct
2 Execution timed out 1094 ms 50960 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 15956 KB Output is correct
2 Execution timed out 1088 ms 52028 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 15896 KB Output is correct
2 Correct 11 ms 15956 KB Output is correct
3 Correct 8 ms 15908 KB Output is correct
4 Execution timed out 1089 ms 16284 KB Time limit exceeded
5 Halted 0 ms 0 KB -