Submission #578322

#	Time	Username	Problem	Language	Result	Execution time	Memory
578322		vanic	Stranded Far From Home (BOI22_island)	C++14	0 / 100	261 ms	40204 KiB

island

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <ctime>
#include <cstdlib>
#include <set>
#include <cstring>

using namespace std;

const int maxn=2e5+5;
typedef long long ll;

struct union_find{
	int parent[maxn];
	ll val[maxn];
	set < pair < int, int > > veze[maxn];
	union_find(){
		for(int i=0; i<maxn; i++){
			parent[i]=i;
		}
	}
	int find(int x){
		if(parent[x]==x){
			return x;
		}
		return parent[x]=find(parent[x]);
	}
	void update(int x, int y){
		x=find(x);
		y=find(y);
		if(veze[x].size()>veze[y].size()){
			swap(x, y);
		}
		val[y]+=val[x];
		parent[x]=parent[y];
		while(!veze[x].empty()){
			veze[y].insert(*veze[x].begin());
			veze[x].erase(veze[x].begin());
		}
	}
	bool query(int x, int y){
		return find(x)==find(y);
	}
	
};

union_find U;
int val[maxn];

int cmp(int a, int b){
	return val[a]<val[b];
}

void bfs(int x){
	pair < int, int > p;
	while(!U.veze[U.find(x)].empty()){
		p=*U.veze[U.find(x)].begin();
		if(U.query(x, p.second)){
			U.veze[U.find(x)].erase(U.veze[U.find(x)].begin());
			continue;
		}
		if(U.val[U.find(x)]>=p.first){
			U.veze[U.find(x)].erase(U.veze[U.find(x)].begin());
			U.update(x, p.second);
		}
		else{
			break;
		}
	}
}

vector < pair < int, ll > > ms[maxn];
int br[maxn];
bool jesam[maxn];
bool dobar[maxn];

ll suma[maxn];
ll prepreka[maxn];
vector < int > kand[maxn];

/*
void rokaj(int x){
	jesam[x]=1;
	suma[x]=U.val[x];
	
	for(int i=0; i<(int)ms[x].size(); i++){
		br[ms[x][i].first]--;
		if(!br[ms[x][i].first]){
			
			rokaj(ms[x][i].first);
		}
	}
}*/

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	srand(time(NULL));
	int n, m;
	cin >> n >> m;
	for(int i=0; i<n; i++){
		cin >> val[i];
		U.val[i]=val[i];
	}
	int a, b;
	for(int i=0; i<m; i++){
		cin >> a >> b;
		a--;
		b--;
		if(val[a]>val[b]){
			U.veze[b].insert({val[a], a});
		}
		else if(val[b]>val[a]){
			U.veze[a].insert({val[b], b});
		}
		else{
			U.veze[b].insert({val[a], a});
			U.veze[a].insert({val[b], b});
		}
	}
	
	for(int i=0; i<n; i++){
		bfs(i);
	}
	set < int > bio;
	int x, y;
	for(int i=0; i<n; i++){
		x=U.find(i);
		if(jesam[x]){
			continue;
		}
		jesam[x]=1;
		bio.clear();
		for(auto j=U.veze[x].begin(); j!=U.veze[x].end(); j++){
			y=U.find(j->second);
			if(bio.find(y)!=bio.end()){
				continue;
			}
			bio.insert(y);
			ms[y].push_back({x, j->first});
			br[x]++;
		}
	}
	memset(jesam, 0, sizeof(jesam));
	for(int i=0; i<n; i++){
		if(br[U.find(i)]==0 && !dobar[U.find(i)]){
			dobar[U.find(i)]=1;
			kand[U.find(i)].push_back(U.find(i));
		}
	}
/*	for(int i=0; i<n; i++){
		if(br[U.find(i)]==0 && !jesam[U.find(i)]){
			rokaj(U.find(i));
		}
	}*/
	for(int i=0; i<n; i++){
		cout << dobar[U.find(i)];
	}
	cout << '\n';
	return 0;
}

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