제출 #586901

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
586901		nots0fast	Stranded Far From Home (BOI22_island)	C++17	100 / 100	379 ms	91640 KiB

island

#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 (int)(pow(10,6) + 10)

ll arr[MAX];

namespace n10{
	int aid[MAX];
	vector<int> dsu[MAX];
	vector<int> good[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];
	}
	bool join(int a,int b){  //	1 - if joined, 0 - if they were already joined 
		int aid1 = aid[a], aid2 = aid[b];
		if(dsu[aid2].size() > dsu[aid1].size())
			swap(aid1,aid2);
		if(aid1==aid2)
			return 0;
		for(auto hd : dsu[aid2]){
			aid[hd] = aid1;
			dsu[aid1].push_back(hd);
		}
		for(auto& hd : good[aid2]){
			good[aid1].pb(hd);
		}
		
		dsu[aid2].clear();
		good[aid2].clear();
		s[aid1]+=s[aid2];
		return 1;
	}
};

using namespace n10;

bool srt(ll i, ll j){
	return arr[i] < arr[j];
}

void deal(){
	ll n, m;
	cin>>n>>m;
	
	vector<vector<ll> > g(n);
	fori(n){
		cin>>arr[i];
	}
	
	ini(n);
	
	fori(m){
		ll ai, bi;
		cin>>ai>>bi;
		--ai, --bi;
		g[ai].pb(bi);
		g[bi].pb(ai);
	}
	
	vector<ll > all;
	fori(n){
		all.pb(i);
	}
	
	sort(all.begin(), all.end(), srt);
	fori(n){
		sort(g[i].begin(), g[i].end(), srt);
	}
	
	for(auto& hd : all){
		for(auto& hr : g[hd]){
			ll aid2 = aid[hr];
			ll aid1 = aid[hd];
			if(s[aid2] < arr[hd]){
			//	cout<<"bad for "<<hr+1<<" because "<<hd+1<<" "<<arr[hd]<<endl;
				good[aid2].clear();
			}
			if(arr[hr] <= s[aid1]){
				join(hr, hd);
			}
		}
	}
	
	ll wh = aid[0];
	vector<bool> ans(n, 0);
	for(auto& el : good[wh]){
		ans[el] = 1;
	}
	
	fori(n){
		cout<<ans[i];
	}
	
}

int main(){
	cin.tie(0);
	ios_base::sync_with_stdio(0);
	deal();
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 15 / 15
• Subtask 4: 30 / 30
• Subtask 5: 35 / 35