oj.uz

답안 #586837

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
586837 2022-06-30T18:01:46 Z nots0fast Stranded Far From Home (BOI22_island) C++17
10 / 100
 745 ms 65864 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<int> 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];
			while(!edg[i].empty()){
				edg[i].pop();
			}
		}
	}
	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);
			}
			good[aid2].clear();
		}
		
		{
			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();
		
		s[aid1]+=s[aid2];
		
		return aid1;
	}
};

using namespace dsu;

bool debug = 0;

void deal(){
	srand(time(NULL));
	
	
	ll n, m;
	if(debug){
		n = 2e2, m = 2e3;
	}
	else{
		cin>>n>>m;
	}
	
	fori(n){
		if(debug){
			arr[i] = rand() % (100);
		}
		else{
			cin>>arr[i];
		}
	}
	ini(n);
	
	/*
	if(debug){
		fori(n-1){
			edg[0].push(mp(arr[i+1],i+1));
			edg[i+1].push(mp(arr[0],0));
		}
	}
	*/
	
	fori(m){
		ll ai, bi;
		if(!debug){
			cin>>ai>>bi;
			--ai, --bi;
		}
		else{
			ai = rand() % n , bi = (ai + rand() % (n-1) + 1)%n;
			assert(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());
		assert(!edg[hd].empty());
		// assert(!all.empty());
		while(1){
			assert(!edg[hd].empty());
			auto it = edg[hd].top();
			ll wh = it.ss;
			if(aid[wh] == hd){
				edg[hd].pop();
				continue;
			}
			else{
				if(s[hd] >= arr[wh]){
					edg[hd].pop();
					ll hr = aid[wh];
					auto it = all.find(mp(s[hr], hr) );
					if(it != all.end()){
						all.erase(it);
					}
					ll cr = join(hd, hr);
					assert(cr != -1);
					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 8 ms 15956 KB Output is correct
2 Correct 11 ms 15924 KB Output is correct
3 Correct 10 ms 15956 KB Output is correct
4 Correct 11 ms 16340 KB Output is correct
5 Correct 11 ms 16328 KB Output is correct
6 Correct 10 ms 16340 KB Output is correct
7 Correct 16 ms 16340 KB Output is correct
8 Correct 9 ms 16212 KB Output is correct
9 Incorrect 13 ms 16340 KB Output isn't correct
10 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 16000 KB Output is correct
3 Correct 444 ms 59588 KB Output is correct
4 Correct 305 ms 52416 KB Output is correct
5 Correct 620 ms 55672 KB Output is correct
6 Correct 567 ms 56840 KB Output is correct
7 Correct 599 ms 56768 KB Output is correct
8 Correct 344 ms 53256 KB Output is correct
9 Correct 375 ms 56636 KB Output is correct
10 Correct 166 ms 52896 KB Output is correct
11 Correct 262 ms 52896 KB Output is correct
12 Correct 436 ms 55652 KB Output is correct
13 Correct 307 ms 51312 KB Output is correct
14 Correct 284 ms 51400 KB Output is correct
15 Correct 259 ms 51412 KB Output is correct
16 Correct 221 ms 50972 KB Output is correct

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 15956 KB Output is correct
2 Correct 745 ms 60816 KB Output is correct
3 Correct 735 ms 63064 KB Output is correct
4 Correct 268 ms 53072 KB Output is correct
5 Incorrect 282 ms 52640 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 15956 KB Output is correct
2 Correct 625 ms 59240 KB Output is correct
3 Correct 614 ms 62604 KB Output is correct
4 Correct 614 ms 61936 KB Output is correct
5 Correct 688 ms 65864 KB Output is correct
6 Correct 602 ms 62748 KB Output is correct
7 Correct 264 ms 54580 KB Output is correct
8 Correct 213 ms 57828 KB Output is correct
9 Correct 305 ms 45964 KB Output is correct
10 Incorrect 634 ms 63792 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 15956 KB Output is correct
2 Correct 11 ms 15924 KB Output is correct
3 Correct 10 ms 15956 KB Output is correct
4 Correct 11 ms 16340 KB Output is correct
5 Correct 11 ms 16328 KB Output is correct
6 Correct 10 ms 16340 KB Output is correct
7 Correct 16 ms 16340 KB Output is correct
8 Correct 9 ms 16212 KB Output is correct
9 Incorrect 13 ms 16340 KB Output isn't correct
10 Halted 0 ms 0 KB -