Submission #581745

#	Time	Username	Problem	Language	Result	Execution time	Memory
581745		amunduzbaev	Stranded Far From Home (BOI22_island)	C++17	0 / 100	274 ms	34916 KiB

island

#include "bits/stdc++.h"
using namespace std;
 
#define ar array
typedef int64_t ll;
#define int ll

const int N = 2e5 + 5;
int a[N], p[N], sz[N], par[N], cmp[N];
int sum[N], is[N], ner[N];
vector<int> edges[N];

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	int n, m; cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		p[i] = i;
	}
	
	for(int i=0;i<m;i++){
		int a, b; cin>>a>>b;
		edges[a].push_back(b);
		edges[b].push_back(a);
	}
	
	sort(p + 1, p + n + 1, [&](int i, int j){
		return a[i] < a[j];
	});
	
	for(int i=1;i<=n;i++){
		cmp[i] = a[i];
		sz[i] = 1;
		par[i] = i;
	}
	vector<vector<ar<int, 2>>> last;
	function<int(int)> f = [&](int x) { return (par[x] == x ? x : f(par[x])); };
	auto merge = [&](int a, int b){
		a = f(a), b = f(b);
		if(a == b) return;
		if(sz[a] < sz[b]) swap(a, b);
		sz[a] += sz[b], par[b] = a;
		cmp[a] += cmp[b];
		last.back().push_back({a, b});
	};
	
	auto add = [&](int v){
		for(auto x : edges[v]){
			if(a[x] > a[v]) continue;
			merge(v, x);
		}
	};
	
	for(int i=1,j=1;i<=n;){
		last.push_back({});
		while(j<=n && a[p[j]] == a[p[i]]){
			add(p[j]);
			j++;
		}
		
		while(i<j){
			sum[p[i]] = cmp[f(p[i])];
			i++;
		}
	}
	//~ cout<<"here"<<endl;
	
	auto rem = [&](){
		reverse(last.back().begin(), last.back().end());
		for(auto [a, b] : last.back()){
			par[b] = b, cmp[a] -= cmp[b], sz[a] -= sz[b];
		} last.pop_back();
	};
	
	for(int i=n,j=n;i>0;){
		while(j>0 && a[p[j]] == a[p[i]]){
			if(sum[p[j]] >= ner[f(p[j])]){
				is[p[j]] |= 1;
			}
			j--;
		}
		rem();
		
		while(i>j){
			if(is[p[i]]){
				for(auto x : edges[p[i]]){
					if(a[x] >= a[p[i]]) continue;
					ner[f(x)] = a[p[i]];
				}
			}
			i--;
		}
	}
	
	for(int i=1;i<=n;i++){
		cout<<is[i];
	} cout<<"\n";
}

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