Submission #967623

#	Time	Username	Problem	Language	Result	Execution time	Memory
967623		dong_gas	Stranded Far From Home (BOI22_island)	C++17	0 / 100	451 ms	60932 KiB

island

#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <bits/extc++.h>
#define all(v) v.begin(), v.end()
#define zip(v) sort(all(v)), v.erase(unique(all(v)), v.end())
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pint;
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
 
ll n, m, a[200020];
 
struct disjoin_set{
	ll papa[200020], height[200020], sum[200020];
	void init() {
		memset(papa,-1,sizeof(papa));
		memset(height,0,sizeof(height));
		for(ll i=1;i<=n;i++) sum[i]=a[i];
	}
	ll Find(ll u) {
		if(papa[u]==-1) return u;
		return papa[u]=Find(papa[u]);
	}
	bool Union(ll u,ll v) {
		u=Find(u), v=Find(v);
		if(u==v) return false;
		if(height[u]<height[v]) swap(u,v);
		papa[v]=u;
		if(height[u]==height[v]) height[u]++;
		sum[u]+=sum[v];
		return true;
	}
} djs;
 
vector<ll> adj[200020], x;
bool chk[200020], visited[200020];
unordered_map<ll, ll> ma;
map<ll, vector<pll>> edges;
 
void dfs(ll u, ll p) {
	visited[u]=1;
	for(ll& v:adj[u]) if(!chk[v] && v!=p && !visited[v]) dfs(v, u);
}
 
void solve() {
    cin>>n>>m;
	for(ll i=1;i<=n;i++) cin>>a[i], x.emplace_back(a[i]);
	zip(x), x.emplace_back(0);
	for(ll i=0;i+1<(ll)x.size();i++) ma[x[i]]=x[i+1];
	while(m --> 0) {
		ll u, v; cin>>u>>v;
		if(a[u]<a[v]) swap(u,v);
		edges[a[u]].emplace_back(u,v);
	}
	for(ll i=1;i<=n;i++) edges[a[i]].emplace_back(i,i);
	djs.init();
 
	for(auto [p, vec]: edges) {
		//cout<<p<<'\n';
		//for(auto [u,v]:vec) cout<<u<<' '<<v<<endl;
		//cout<<endl;
		ll nxt_val=ma[p];
		set<ll> s;
		for(auto [u, v]: vec) {
			if(djs.Union(u,v)) adj[u].emplace_back(v), adj[v].emplace_back(u);
			s.insert(u), s.insert(v);
		}
		for(auto u: s) {
			if(djs.sum[djs.Find(u)]<nxt_val) chk[u]=1;
		}
		//cout<<nxt_val<<endl;
	}
	//for(ll i=1;i<=n;i++) cout<<chk[i];
	//cout<<endl;
	for(ll i=1;i<=n;i++) if(a[i]==x[x.size()-2] && !visited[i]) dfs(i,0);
	for(ll i=1;i<=n;i++) cout<<visited[i];
	
}
 
int main() {
    cin.tie(0)->sync_with_stdio(0);
    int tc=1; //cin>>tc;
    while(tc--) solve();
} 

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