oj.uz

Submission #586748

# Submission time Handle Problem Language Result Execution time Memory
586748 2022-06-30T15:56:12 Z nots0fast Stranded Far From Home (BOI22_island) C++17
10 / 100
 1000 ms 78112 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<ll, ll> , vector<pair<ll, ll> > , greater<pair<ll, ll> > > 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();
				edg[aid2].pop();
				edg[aid1].push(tp);
			}
		}
		
		
		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

# Verdict Execution time Memory Grader output
1 Correct 8 ms 15884 KB Output is correct
2 Correct 8 ms 15956 KB Output is correct
3 Correct 8 ms 15956 KB Output is correct
4 Execution timed out 1088 ms 16340 KB Time limit exceeded
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 9 ms 15968 KB Output is correct
3 Correct 461 ms 78112 KB Output is correct
4 Correct 337 ms 57736 KB Output is correct
5 Correct 639 ms 66344 KB Output is correct
6 Correct 629 ms 67460 KB Output is correct
7 Correct 699 ms 68036 KB Output is correct
8 Correct 374 ms 59808 KB Output is correct
9 Correct 402 ms 64412 KB Output is correct
10 Correct 214 ms 54460 KB Output is correct
11 Correct 299 ms 54460 KB Output is correct
12 Correct 543 ms 61800 KB Output is correct
13 Correct 382 ms 55600 KB Output is correct
14 Correct 297 ms 55468 KB Output is correct
15 Correct 334 ms 60696 KB Output is correct
16 Correct 193 ms 58144 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 15956 KB Output is correct
2 Execution timed out 1087 ms 55104 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 15956 KB Output is correct
2 Execution timed out 1065 ms 55376 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 15884 KB Output is correct
2 Correct 8 ms 15956 KB Output is correct
3 Correct 8 ms 15956 KB Output is correct
4 Execution timed out 1088 ms 16340 KB Time limit exceeded
5 Halted 0 ms 0 KB -