Submission #1234498

#	Time	Username	Problem	Language	Result	Execution time	Memory
1234498		PlayVoltz	Stranded Far From Home (BOI22_island)	C++20	100 / 100	210 ms	51620 KiB

island

#include <cstdio>
#include <stdio.h>
#include <stdbool.h>
#include <iostream>
#include <map>
#include <vector>
#include <climits>
#include <stack>
#include <string>
#include <queue>
#include <algorithm>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <cmath>
#include <cctype>
#include <bitset>
#include <iomanip>
#include <cstring>
#include <numeric>
#include <cassert>
using namespace std;

#define int long long
#define pii pair<int, int>
#define mp make_pair
#define pb push_back
#define fi first
#define se second

vector<int> dsu, val, ooga;
vector<vector<int> > all;
vector<bool> ans;

int fp(int a){
	if (dsu[a]==-1)return a;
	return dsu[a]=fp(dsu[a]);
}

void merge(int a, int b){
	a=fp(a), b=fp(b);
	if (a==b)return;
	if (ooga[b]>val[a])for (auto c:all[a])ans[c]=0;
	if (all[b].size()<all[a].size())swap(all[a], all[b]);
	for (auto c:all[a])all[b].pb(c);
	val[b]+=val[a];
	dsu[a]=b;
}

int32_t main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n, m, a, b;
	cin>>n>>m;
	vector<pii> vect(n+1);
	ooga.resize(n+1);
	ans.resize(n+1, 1);
	all.resize(n+1);
	dsu.resize(n+1, -1);
	val.resize(n+1, 0);
	vector<vector<int> > graph(n+1);
	for (int i=1; i<=n; ++i)cin>>vect[i].fi, vect[i].se=i, val[i]=vect[i].fi, all[i].pb(i), ooga[i]=vect[i].fi;
	sort(vect.begin(), vect.end());
	while (m--){
		cin>>a>>b;
		graph[a].pb(b);
		graph[b].pb(a);
	}
	for (auto c:vect)for (auto num:graph[c.se])if (ooga[c.se]>=ooga[num])merge(num, c.se);
	for (int i=1; i<=n; ++i)cout<<ans[i];
}

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