Submission #1305493

#	Time	Username	Problem	Language	Result	Execution time	Memory
1305493		coolboy19521	Stranded Far From Home (BOI22_island)	C++20	0 / 100	228 ms	15652 KiB

island

#include "bits/stdc++.h"

#define FOR(i,a,b)for(int i=(a);i<(b);i++)
#define F0R(i,a)FOR(i,0,a)
#define ROF(i,a,b)for(int i=(b)-1;i>=(a);i--)
#define R0F(i,a)ROF(i,0,a)
#define REP(a)F0R(_,a)

using namespace std;

const int mxn=2e5+20;

vector<int> aj[mxn];
int s[mxn],d[mxn];
bool mark[mxn];

struct{
	int ar[mxn],val[mxn];
	void init(int n){
		fill_n(ar,n,-1);
		memcpy(val,s,sizeof(val));
	}
	int find(int u){
		if(ar[u]<0)return u;
		else return ar[u]=find(ar[u]);
	}
	void unite(int u,int v){
		v=find(v);
		if(d[s[u]]>val[v]){
			mark[v]=true;
			return;
		}
		u=find(u);
		if(u==v)return;
		if(ar[u]>ar[v])swap(u,v);
		val[u]+=val[v],ar[u]+=ar[v],ar[v]=u;
	}
}DSU;

int main(){
	int n,m;cin>>n>>m;
	F0R(i,n)cin>>s[i];
	DSU.init(n);
	vector<int>c(n);
	F0R(i,n)c[i]=s[i];
	sort(begin(c),end(c));
	c.erase(unique(begin(c),end(c)),end(c));
	F0R(i,n){
		int nw=lower_bound(begin(c),end(c),s[i])-begin(c);
		d[nw]=s[i],s[i]=nw;
	}
	REP(m){
		int a,b;cin>>a>>b;
		a--,b--;
		if(s[a]<s[b])swap(a,b);
		aj[a].push_back(b);
	}
	vector<pair<int,int>>vp;
	F0R(i,n)vp.emplace_back(s[i],i);
	sort(begin(vp),end(vp));
	for(auto&pr:vp){
		int w=pr.first,u=pr.second;
		for(int v:aj[u])DSU.unite(u,v);
		if(w==c.size()-1)break;
	}
	F0R(i,n)cout<<(mark[DSU.find(i)]?0:1);cout<<'\n';
}

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