Submission #577319

#	Time	Username	Problem	Language	Result	Execution time	Memory
577319		jamielim	Stranded Far From Home (BOI22_island)	C++14	100 / 100	339 ms	43172 KiB

island

#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define mp make_pair
#define pb emplace_back
#define ALL(x) x.begin(),x.end()
#define SZ(x) (int)x.size()
typedef long long ll;
typedef pair<int,int> ii;
typedef pair<ii,ii> i4;
const int MOD=1000000007;
const int INF=1012345678;
const ll LLINF=1012345678012345678LL;
const double PI=3.1415926536;
const double EPS=1e-14;

int n,m;
ll s[200005];
vector<int> ordered[200005];
vector<int> adj[200005];
bool imposs[200005];
bool exist[200005];
int par[200005];
ll sz[200005];
vector<int> sets[200005];

int root(int x){
	return par[x]=(par[x]==x?x:root(par[x]));
}

void merge(int x,int y){
	int ra=root(x),rb=root(y);
	if(ra==rb)return;
	if(SZ(sets[ra])<SZ(sets[rb])){
		swap(ra,rb);
		swap(x,y);
	}
	// rb is smaller
	for(int i:sets[rb])sets[ra].pb(i);
	sz[ra]+=sz[rb];
	par[rb]=ra;
}

void mark_imposs(int x){
	for(int i:sets[x]){
		imposs[i]=1;
	}
	sets[x].clear();
}

int main(){
	scanf("%d%d",&n,&m);
	vector<ll> disc;
	for(int i=1;i<=n;i++){
		scanf("%lld",&s[i]);
		disc.pb(s[i]);
	}
	sort(ALL(disc));
	disc.resize(unique(ALL(disc))-disc.begin());
	for(int i=1;i<=n;i++){
		int x=lower_bound(ALL(disc),s[i])-disc.begin();
		ordered[x].pb(i);
	}
	int a,b;
	for(int i=0;i<m;i++){
		scanf("%d%d",&a,&b);
		adj[a].pb(b);
		adj[b].pb(a);
	}
	for(int i=1;i<=n;i++){
		par[i]=i;
		sz[i]=s[i];
		sets[i].pb(i);
	}
	for(int i=0;i<SZ(disc);i++){
		for(int j:ordered[i]){
			exist[j]=1;
		}
		for(int j:ordered[i]){
			for(int k:adj[j]){
				int p=root(k),q=root(j);
				if(p==q)continue;
				if(exist[p]){
					if(sz[p]<disc[i]&&!imposs[p]){
						mark_imposs(p);
					}
					merge(q,p);
				}
			}
		}
	}
	for(int i=1;i<=n;i++){
		if(imposs[i])printf("0");
		else printf("1");
	}
}

Compilation message (stderr)

island.cpp: In function 'int main()':
island.cpp:54:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   54 |  scanf("%d%d",&n,&m);
      |  ~~~~~^~~~~~~~~~~~~~
island.cpp:57:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   57 |   scanf("%lld",&s[i]);
      |   ~~~~~^~~~~~~~~~~~~~
island.cpp:68:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   68 |   scanf("%d%d",&a,&b);
      |   ~~~~~^~~~~~~~~~~~~~

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