oj.uz

Submission #648236

# Submission time Handle Problem Language Result Execution time Memory
648236 2022-10-05T19:17:08 Z beaconmc Stranded Far From Home (BOI22_island) C++14
0 / 100
 336 ms 25788 KB 
#include <bits/stdc++.h>

typedef int ll;
using namespace std;


#define FOR(i, x, y) for(ll i=x; i<y; i++)
#define FORNEG(i, x, y) for(ll i=x; i>y; i--)
#define fast() ios_base::sync_with_stdio(false);cin.tie(NULL)


ll cc[200001];
ll siz[200001];
ll sizes[200001];
vector<ll> stuff[200001];
ll ans[200001];
vector<vector<ll>> edges;

ll n,m;
int find(ll a){
	while (cc[a] != a){
		cc[a] = cc[cc[a]];
		a = cc[a];
	}
	return a;
}

void unite(ll a,ll b){
	ll aa = find(a);
	ll bb = find(b);
	if (aa==bb) return;

	if (siz[aa] < sizes[b]){
		for (auto&i : stuff[aa]){
			ans[i] = 0;
		}
		stuff[aa] = {};
	}
	if (siz[bb] < sizes[a]){
		for (auto&i : stuff[bb]){
			ans[i] = 0;
		}
		stuff[bb] = {};
	}

	if (stuff[aa].size() > stuff[bb].size()){
		swap(stuff[aa], stuff[bb]);
	}
	for (auto&i : stuff[aa]){
		stuff[bb].push_back(i);
	}

	siz[bb] += siz[aa];
	cc[aa] = bb;
}

int main(){
	cin >> n >> m;
	FOR(i,0,n){
		cc[i] = i;
		cin >> sizes[i];
		siz[i] = sizes[i];
		stuff[i].push_back(i);
		ans[i] = 1;
	}
	FOR(i,0,m){
		ll a,b;
		cin >> a >> b;
		a--;b--;
		edges.push_back({max(sizes[a],sizes[b]),min(sizes[a],sizes[b]), a,b});
	}

	sort(edges.begin(), edges.end());

	for (auto&i : edges){
		unite(i[2],i[3]);
	}
	FOR(i,0,n) cout << ans[i];


}

Subtask #1
0 / 10.0

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

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Incorrect 283 ms 25788 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Incorrect 325 ms 25472 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Incorrect 336 ms 25508 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

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