oj.uz

Submission #586834

# Submission time Handle Problem Language Result Execution time Memory
586834 2022-06-30T18:00:40 Z nots0fast Stranded Far From Home (BOI22_island) C++17
10 / 100
 577 ms 105520 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();
			edg[hd].pop();
			ll wh = it.ss;
			if(aid[wh] == hd){
				continue;
			}
			else{
				if(s[hd] >= arr[wh]){
					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

# Verdict Execution time Memory Grader output
1 Correct 8 ms 15956 KB Output is correct
2 Correct 8 ms 15956 KB Output is correct
3 Correct 7 ms 15956 KB Output is correct
4 Runtime error 21 ms 32852 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 15956 KB Output is correct
2 Correct 10 ms 15956 KB Output is correct
3 Correct 409 ms 59588 KB Output is correct
4 Correct 287 ms 52344 KB Output is correct
5 Correct 532 ms 55540 KB Output is correct
6 Correct 530 ms 56836 KB Output is correct
7 Correct 577 ms 56668 KB Output is correct
8 Correct 378 ms 53348 KB Output is correct
9 Correct 333 ms 56500 KB Output is correct
10 Correct 157 ms 52920 KB Output is correct
11 Correct 276 ms 52916 KB Output is correct
12 Correct 418 ms 55704 KB Output is correct
13 Correct 318 ms 51380 KB Output is correct
14 Correct 279 ms 51332 KB Output is correct
15 Correct 242 ms 51360 KB Output is correct
16 Correct 197 ms 50936 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 15956 KB Output is correct
2 Runtime error 507 ms 103376 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 15956 KB Output is correct
2 Runtime error 252 ms 105520 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 15956 KB Output is correct
2 Correct 8 ms 15956 KB Output is correct
3 Correct 7 ms 15956 KB Output is correct
4 Runtime error 21 ms 32852 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -