Submission #1163072

#	Time	Username	Problem	Language	Result	Execution time	Memory
1163072		WH8	Stranded Far From Home (BOI22_island)	C++20	100 / 100	227 ms	43376 KiB

island

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#define pb push_back
#define int long long 
#define f first
#define s second
#define pll pair<long long, long long>

int v[200005], p[200005], gv[200005];
vector<vector<int>> pi(200005);
vector<vector<int>> al(200005);
int par(int x){
	if(p[x]==-1)return x;
	return p[x]=par(p[x]);
}
void merge(int a, int b){ // b is the new node that we are inserting
	//~ printf("merging %lld, %lld\n", a,b);
	int x=par(a), y=par(b);
	if(x==y)return;
	//~ cout<<"here\n";
	if(gv[x] < v[b]){
		pi[x].clear();
		p[x]=y;
		gv[y]+=gv[x];
	}
	else{
		if(pi[x].size()<pi[y].size())swap(x,y);
		for(auto it:pi[y])pi[x].push_back(it);
		gv[x]+=gv[y];
		p[y]=x;
	}
}

signed main(){
	int n, m;cin>>n>>m;
	vector<pll> nodes;
	for(int i=0;i<n;i++){
		p[i]=-1;
		cin>>v[i];
		gv[i]=v[i];
		pi[i].push_back(i);
		nodes.push_back({v[i], i});
	}
	sort(nodes.begin(),nodes.end());
	for(int i=0;i<m;i++){
		int a,b;cin>>a>>b;
		a--, b--;
		al[a].push_back(b);
		al[b].push_back(a);
	}
	for(int i=0;i<n;i++){
		int cn=nodes[i].s;
		for(auto it:al[cn]){
			if(v[it]<=v[cn]){
				merge(it, cn);
			}
		}
		//~ for(int j=0;j<n;j++){
			//~ cout<<p[j]<<" "<<gv[j]<<" "<<v[j]<<" : ";
			//~ for(auto it:pi[j])cout<<it<<" ";
			//~ cout<<endl;
		//~ }
	}
	vector<bool> ans(n, 0);
	int h=par(0);
	for(auto it:pi[h]){
		ans[it]=true;
	}
	for(auto it:ans)cout<<it;
}

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