oj.uz

Submission #651743

# Submission time Handle Problem Language Result Execution time Memory
651743 2022-10-19T23:26:00 Z inksamurai Stranded Far From Home (BOI22_island) C++17
0 / 100
 243 ms 27220 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];
	}

	vi ert;
	rep(i,n){
		ert.pb(i);		
	}
	sort(ert.begin(),ert.end(),[&](const int&l,const int&r){
		return a[l]<a[r];
	});

	vi pns(n,1);
	rep(i,n){
		int v=ert[i];
		for(auto u:adj[v]){
			if(a[v]>=a[u]){
				int up=uf.parent(u);
				int now=uf.leb[up];
				if(now<a[v]){
					for(auto rbt:uf.rbts[up]){
						pns[rbt]=0;
					}
					uf.rbts[up].clear();
				}
				uf.merge(v,up);
			}
		}
	}

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

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Incorrect 2 ms 468 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 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Incorrect 143 ms 27220 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

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

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 214 ms 27128 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 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Incorrect 2 ms 468 KB Output isn't correct
5 Halted 0 ms 0 KB -