oj.uz

Submission #586777

# Submission time Handle Problem Language Result Execution time Memory
586777 2022-06-30T17:01:18 Z nots0fast Stranded Far From Home (BOI22_island) C++17
10 / 100
 637 ms 105432 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){
			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);
					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 8 ms 15956 KB Output is correct
4 Runtime error 23 ms 32940 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 8 ms 15956 KB Output is correct
3 Correct 474 ms 64248 KB Output is correct
4 Correct 284 ms 52300 KB Output is correct
5 Correct 597 ms 60512 KB Output is correct
6 Correct 592 ms 61560 KB Output is correct
7 Correct 637 ms 62472 KB Output is correct
8 Correct 381 ms 54140 KB Output is correct
9 Correct 384 ms 60748 KB Output is correct
10 Correct 180 ms 52884 KB Output is correct
11 Correct 317 ms 52896 KB Output is correct
12 Correct 438 ms 56000 KB Output is correct
13 Correct 291 ms 51396 KB Output is correct
14 Correct 287 ms 51368 KB Output is correct
15 Correct 255 ms 52948 KB Output is correct
16 Correct 181 ms 52532 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 15900 KB Output is correct
2 Runtime error 529 ms 103268 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 226 ms 105432 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 8 ms 15956 KB Output is correct
4 Runtime error 23 ms 32940 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -