oj.uz

Submission #586742

# Submission time Handle Problem Language Result Execution time Memory
586742 2022-06-30T15:34:39 Z nots0fast Stranded Far From Home (BOI22_island) C++17
10 / 100
 1000 ms 94984 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];
	set<pair<ll, ll> > edg[MAX];	// which node, what is the value
	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]);
			}
			for(auto& el : edg[aid2]){
				edg[aid1].insert(el);
			}
		}
		
		
		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;

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].insert(mp(arr[bi], bi));
		edg[bi].insert(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].begin();
			edg[hd].erase(edg[hd].begin());
			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 10 ms 19060 KB Output is correct
2 Correct 12 ms 19028 KB Output is correct
3 Correct 10 ms 19028 KB Output is correct
4 Execution timed out 1073 ms 19540 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 19132 KB Output is correct
2 Correct 9 ms 19024 KB Output is correct
3 Correct 730 ms 94984 KB Output is correct
4 Correct 434 ms 77992 KB Output is correct
5 Correct 797 ms 81096 KB Output is correct
6 Correct 763 ms 83128 KB Output is correct
7 Correct 837 ms 83244 KB Output is correct
8 Correct 637 ms 79080 KB Output is correct
9 Correct 572 ms 77976 KB Output is correct
10 Correct 353 ms 73960 KB Output is correct
11 Correct 500 ms 75952 KB Output is correct
12 Correct 739 ms 78300 KB Output is correct
13 Correct 456 ms 74432 KB Output is correct
14 Correct 420 ms 75488 KB Output is correct
15 Correct 463 ms 75844 KB Output is correct
16 Correct 264 ms 73948 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 19104 KB Output is correct
2 Execution timed out 1070 ms 76128 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 19028 KB Output is correct
2 Execution timed out 1046 ms 74644 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 19060 KB Output is correct
2 Correct 12 ms 19028 KB Output is correct
3 Correct 10 ms 19028 KB Output is correct
4 Execution timed out 1073 ms 19540 KB Time limit exceeded
5 Halted 0 ms 0 KB -