Submission #972021

#	Time	Username	Problem	Language	Result	Execution time	Memory
972021		NintsiChkhaidze	Stranded Far From Home (BOI22_island)	C++17	100 / 100	354 ms	50156 KiB

island

#include <bits/stdc++.h>
#define s second
#define f first
#define pb push_back
#define pii pair <int,int>
#define int long long
using namespace std;
 
const int N = 2e5 + 5;
int p[N],sz[N],ans[N];
pii b[N];
bool active[N];
vector <int> v[N],vec,cmp[N];
set <pii> st;
 
int P(int x){
	if(x==p[x]) return x;
	return p[x]=P(p[x]);
}
 
void dsu(int x,int y){
	int px=P(x),py=P(y);
	if (px==py) return;
 
	st.erase(st.find({sz[px],px})); 
	st.erase(st.find({sz[py],py}));
	
	if (cmp[px].size() < cmp[py].size()) swap(px,py);
	sz[px] += sz[py];
	for (int k: cmp[py])
		cmp[px].pb(k);
 
	cmp[py].clear();
	sz[py]=0;
	st.insert({sz[px],px});
	p[py] = px;
}
 
void go(int x){
	active[x] = 1;
	st.insert({sz[x],x});
	for (int to: v[x]){
		if (active[to]){
			if (!ans[to]){
				int pto=P(to);
				st.insert({sz[pto],pto});
			}
			dsu(x,to);
		}
	}
}
 
signed main(){
	ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL);
 
	int n,m;
	cin>>n>>m;	
 
	for (int i = 1; i <= n; i++){
		int a;
		cin>>a;
		sz[i] = a;
		p[i] = i;
		cmp[i].pb(i);
		b[i] = {a,i};
		vec.pb(a);
		ans[i]=1;
	}
	sort(vec.begin(),vec.end());
	vec.erase(unique(vec.begin(),vec.end()),vec.end());
 
	sort(b+1,b+n+1);
	for (int i=1;i<=m;i++){
		int a,bb;
		cin>>a>>bb;
		v[a].pb(bb);
		v[bb].pb(a);
	}
 
	int l = 1;
	for (int i=0;i<vec.size();i++){

		while (l <= n && b[l].f == vec[i]){
			go(b[l].s);
			++l;
		}
 
		if (i + 1 < vec.size()){
			int nxt = vec[i + 1];
			while (st.size() && (st.begin()->f) < nxt){
				int vert = st.begin()->s;
				for (int y: cmp[vert])
					ans[y]=0;
				cmp[vert].clear();
				
				st.erase(st.begin());
				st.insert({});
			}
		}
	}
 
	for (int i=1;i<=n;i++)
		cout<<ans[i];
}	

Compilation message (stderr)

island.cpp: In function 'int main()':
island.cpp:81:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |  for (int i=0;i<vec.size();i++){
      |               ~^~~~~~~~~~~
island.cpp:88:13: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |   if (i + 1 < vec.size()){
      |       ~~~~~~^~~~~~~~~~~~

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