Submission #966371

#	Time	Username	Problem	Language	Result	Execution time	Memory
966371		NotLinux	Stranded Far From Home (BOI22_island)	C++17	0 / 100	1046 ms	142296 KiB

island

//author : FatihCihan
#include <bits/stdc++.h>
using namespace std;
#define all(v) v.begin() , v.end()
#define sz(a) (int)a.size()
const int N = 2e5 + 7;
const int inf = 1e9 + 7;
int n,m,s[N],marked[N],ans[N],tar[N],sum[N],bruh[N];
vector < int > graph[N],adj[N];
struct Component{
	set < pair < int , int > > edges;// outgoing edges of the component
	int parent , representative , value;
} dsu[N];
int find(int a){
	if(dsu[a].parent == dsu[a].representative)return dsu[a].representative;
	else return dsu[a].parent = find(dsu[a].parent);
}
void merge(int a , int b){
	a = find(a) , b = find(b);
	if(a == b)return;
	if(sz(dsu[a].edges) > sz(dsu[b].edges))dsu[a].edges.swap(dsu[b].edges);
	dsu[a].parent = dsu[b].representative;
	dsu[b].value += dsu[a].value;
	vector < pair < int , int > > will_delete;
	// cout << "merge : " << a << " , " << b << endl;
	// cout << "edges of a : ";for(auto itr : dsu[a].edges)cout << itr.first << "," << itr.second << "   ";cout << endl;
	// cout << "edges of b : ";for(auto itr : dsu[b].edges)cout << itr.first << "," << itr.second << "   ";cout << endl;
	for(auto itr : dsu[a].edges){
		if(dsu[b].edges.count({itr.second , itr.first}) == 0){
			dsu[b].edges.insert(itr);				
		}
		else{
			will_delete.push_back({itr.second , itr.first});
		}
	}
	for(auto itr : will_delete){
		dsu[b].edges.extract(itr);
	}
	dsu[a].edges.clear();
	// cout << "final of b : ";for(auto itr : dsu[b].edges)cout << itr.first << "," << itr.second << "   ";cout << endl;
}
void solve(){
	cin >> n >> m;
	pair < int , int > village[n];
	vector < int > compr;
	for(int i = 1;i<=n;i++){
		cin >> s[i];
		compr.push_back(s[i]);
		village[i-1] = {s[i] , i};
		dsu[i].representative = dsu[i].parent = i;
		dsu[i].value = s[i];
		tar[i] = inf;
	}
	sort(all(compr));
	compr.resize(unique(all(compr)) - compr.begin());
	sort(village , village + n);
	for(int i = 0;i<m;i++){
		int ai,bi;
		cin >> ai >> bi;
		dsu[ai].edges.insert({ai , bi});
		dsu[bi].edges.insert({bi , ai});
		graph[ai].push_back(bi);
		graph[bi].push_back(ai);
	}
	int lp0 = 0 , lp1 = 0;
	for(auto si : compr){
		while(lp1 < n and village[lp1].first <= si){
			marked[village[lp1].second] = 1;
			lp1++;
		}
		while(lp0 < n and village[lp0].first <= si){
			for(auto itr : graph[village[lp0].second]){
				if(marked[itr] == 1){
					merge(itr , village[lp0].second);
				}
			}
			for(auto itr : dsu[find(village[lp0].second)].edges){
				adj[itr.second].push_back(village[lp0].second);
			}
			bruh[village[lp0].second] = find(village[lp0].second);
			sum[village[lp0].second] = dsu[village[lp0].second].value;
			lp0++;
		}
	}
	for(int i = 1;i<=n;i++){
		sort(all(adj[village[i].second]));
		adj[village[i].second].resize(unique(all(adj[village[i].second])) - adj[village[i].second].begin());
	}
	// cout << "dsu : " << endl;
	// for(int i = 1;i<=n;i++){
	// 	cout << "	" << i << endl;
	// 	for(auto itr : adj[i])cout << "		" << itr << " ";cout << endl;
	// }
	// cout << "###########################################################################" << endl;
	memset(ans , -1 , sizeof(ans));
	tar[village[n-1].second] = 0;
	for(int i = n-1;i>=0;i--){
		// cout << village[i].second << " : " << bruh[village[i].second] << endl;
		if(bruh[village[i].second] == village[i].second){
			if(tar[village[i].second] <= sum[village[i].second]){
				ans[village[i].second] = 1;
				for(auto itr : adj[village[i].second]){
					tar[itr] = min(tar[itr] , s[village[i].second]);
				}
			}
			else ans[village[i].second] = 0;
		}
	}
	for(int i = 1;i<=n;i++){
		cout << ans[bruh[i]];
	}
	cout << endl;
}
signed main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	int testcase = 1;//cin >> testcase;
	while(testcase--)solve();
	cerr << 1000.0 * clock() / CLOCKS_PER_SEC << " ms" << endl;
}

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