Submission #1122838

#	Time	Username	Problem	Language	Result	Execution time	Memory
1122838		peacebringer1667	Stranded Far From Home (BOI22_island)	C++17	100 / 100	354 ms	32832 KiB

island

#include<bits/stdc++.h>
#define ll long long
#define ldb long double
#define db double
#define fi first
#define se second
#define sza(a) (int)a.size()
#define pir pair<int,int>
#define pirll pair<ll,ll>
using namespace std;
const int maxn = 2e5 + 5;

template <class t1,class t2> inline void maxi(t1 &x,t2 y){if (x < y) x = y;}
template <class t1,class t2> inline void mini(t1 &x,t2 y){if (x > y) x = y;}

template <class t1> void simplify(t1 &x){
	sort(x.begin(),x.end());
	x.erase(unique(x.begin(),x.end()),x.end());
}

int a[maxn];
vector <int> vec[maxn];

void input(int n,int m){
	for (int i = 1 ; i <= n ; i++) cin >> a[i];
	
	while (m--){
		int u,v;
		cin >> u >> v;
		vec[u].push_back(v);
		vec[v].push_back(u);
	}
}

namespace subtask1{
	bool subtask1(int n,int m){
		return max(n,m) <= 2000;
	}
	
	bool mark[maxn];
	set <pir> s;
	
	void refresh(int n){
		s.clear();
		for (int i = 1 ; i <= n ; i++) mark[i] = 0;
	}
	
	bool check(int source,int n){
		//starting from source
    	refresh(n);
    	ll sum = 0;
		
		s.insert({0,source});
        while (s.size()){
        	pir t = *s.begin();
        	s.erase(t);
        	
        	int u = t.se;
        	if (mark[u] || t.fi > sum) continue;
        	mark[u] = 1;
        	sum += a[u];
        	
        	for (int v : vec[u])
        	  if (!mark[v])
        	    s.insert({a[v],v});
		}	
		
		return all_of(mark + 1,mark + 1 + n,[](bool x){return x;});	
	}
	
	void solve(int n,int m){
		for (int i = 1 ; i <= n ; i++)
		 cout << check(i,n);
	}
}

namespace subfull{
	struct dsu{
		int id[maxn];
		ll sum[maxn];
		vector <int> lst[maxn];
		
		void init(int n){
			for (int i = 1 ; i <= n ; i++)
			   id[i] = i,lst[i].push_back(i),sum[i] = a[i];
		}
		
		int fid(int x){
			return (x == id[x]) ? x : id[x] = fid(id[x]);
		}
		
		//small to large, n log n
		void add(int u,int v){
			int x = fid(u),y = fid(v);
			if (x == y) return;
	
			if (lst[x].size() < lst[y].size()) swap(x,y);
			
			id[y] = x;
			sum[x] += sum[y];
			
			for (int t : lst[y]) lst[x].push_back(t);
		}
		
		inline ll getsum(int x){
			return sum[fid(x)];
		}
		
		inline void purge(int x){
			lst[fid(x)].clear();
		}
	} dsu;
	
	vector <pir> traverse_order;
	bool res[maxn],mark[maxn];
	
	void generate_traverse_order(int n){
		for (int i = 1 ; i <= n ; i++)
		   traverse_order.push_back({a[i],i});
		sort(traverse_order.begin(),traverse_order.end());
	}
	
	void add_to_island(int u){
		vector <int> components;
		
		for (int v : vec[u])
		    if (mark[v])
		        components.push_back(dsu.fid(v));
		
		simplify(components);
		
		for (int comp : components)
		  if (dsu.getsum(comp) < a[u])
		      dsu.purge(comp);
		
		for (int comp : components)
		   dsu.add(comp,u);
	}
	
	void solve(int n){
		for (pir t : traverse_order){
			int u = t.se;
			add_to_island(u);
			
			mark[u] = 1;
		}
	}
	
	void prepare_answer(int n){
		for (int i = 2 ; i <= n ; i++)
		  if (dsu.fid(i) != dsu.fid(i - 1)) return;
		
		for (int x : dsu.lst[dsu.fid(1)]) 
		  res[x] = 1;
	}
	
	void solve(int n,int m){
		dsu.init(n);
		
		generate_traverse_order(n);
		
		solve(n);
		
		prepare_answer(n);
		
		for (int u = 1 ; u <= n ; u++) cout << res[u];
	}
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	
////	freopen("ISLAND.inp","r",stdin);
////	freopen("ISLAND.out","w",stdout);
	
	int n,m;
	cin >> n >> m;
	input(n,m);
	
	if (subtask1::subtask1(n,m)){
		subtask1::solve(n,m);
		return 0;
	}
	
	subfull::solve(n,m);

	return 0;
}

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