oj.uz

Submission #651728

# Submission time Handle Problem Language Result Execution time Memory
651728 2022-10-19T22:16:25 Z inksamurai Stranded Far From Home (BOI22_island) C++17
0 / 100
 419 ms 68368 KB 
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define rng(i,c,n) for(int i=c;i<n;i++)
#define fi first
#define se second
#define pb push_back
#define sz(a) (int)a.size()
#define vec(...) vector<__VA_ARGS__>
#define _3CZAtRo ios::sync_with_stdio(0),cin.tie(0)
typedef long long ll;
using pii=pair<int,int>;
using vi=vector<int>;
void print(){cout<<'\n';}
template<class h,class...t>
void print(const h&v,const t&...u){cout<<v<<' ',print(u...);}

struct dsu{
	int n,cmps;
	vi par,si,leb;
	vec(vi) rbts;
	vec(set<pii>) evs;
	dsu(int _n=0){init(_n);}
	void init(int _n){
		n=_n;
		cmps=n;
		par.clear();
		si.clear();
		leb.clear();
		rbts.clear();
		evs.clear();
		par.resize(n);
		si.resize(n);
		leb.resize(n);
		rbts.resize(n);
		evs.resize(n);
		rep(i,n){
			par[i]=i;
			si[i]=1;
			rbts[i].pb(i);
		}
	}
	void merge(int a,int b){
		if(same(a,b)) return;
		cmps-=1;
		int u=parent(a);
		int v=parent(b);
		if(si[u]<si[v])swap(u,v);
		for(auto p:evs[v]){
			evs[u].insert(p);
		}
		for(auto x:rbts[v]){
			rbts[u].pb(x);
		}
		leb[u]+=leb[v];
		si[u]+=si[v];
		par[v]=u;
	}
	int parent(int v){return par[v]=par[v]==v?v:parent(par[v]);}
	bool same(int u,int v){return parent(v)==parent(u);}
	int size(int v=-1){return v==-1?cmps:si[parent(v)];}
};

signed main(){
_3CZAtRo;
	int n,m;
	cin>>n>>m;

	vi a(n);
	rep(i,n){
		cin>>a[i];
	}
	vec(vi) adj(n);
	rep(_,m){
		int u,v;
		cin>>u>>v;
		u-=1,v-=1;
		adj[u].pb(v);
		adj[v].pb(u);
	}

	dsu uf(n);
	rep(v,n){
		uf.leb[v]=a[v];
		for(auto u:adj[v]){
			uf.evs[v].insert({a[u],u});
		}
	}

	set<pii> st;
	rep(v,n){
		st.insert({a[v],v});
	}

	vi pns(n,1);
	while(sz(st)){
		auto ti=st.begin();
		st.erase(ti);
		pii state=*ti;
		int rt=uf.parent(state.se);
		int cnt=state.fi;
		if(uf.leb[rt]!=cnt) continue;
		if(uf.si[rt]==n) break;
		{
			while(sz(uf.evs[rt])){
				auto it=uf.evs[rt].begin();
				pii p=*it;
				if(uf.same(p.se,rt)){
					uf.evs[rt].erase(it);
					continue;
				}
				if(uf.leb[rt]>=uf.leb[p.se]){
					uf.evs[rt].erase(it);
					uf.merge(rt,p.se);
					rt=uf.parent(rt);
				}
				break;
			}
		}
		// print(rt);
		if(uf.leb[rt]==cnt){
			for(auto v:uf.rbts[rt]){
				pns[v]=0;
			}
		}
	}

	rep(i,n){
		cout<<pns[i];
	}
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 324 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Incorrect 3 ms 852 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Incorrect 256 ms 68368 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 419 ms 67948 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 373 ms 68072 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 324 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Incorrect 3 ms 852 KB Output isn't correct
5 Halted 0 ms 0 KB -