oj.uz

답안 #790494

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
790494 2023-07-22T17:44:02 Z esomer Stranded Far From Home (BOI22_island) C++17
0 / 100
 277 ms 46064 KB 
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

struct DSU{
	vector<int> v;
	vector<ll> sum;
	vector<set<pair<int, int>>> adj;
	
	void init(vector<pair<int, int>>& a, vector<vector<pair<int, int>>>& adj1){
		int n = (int)a.size();
		v.assign(n, -1);
		sum.assign(n, 0);
		adj.assign(n, {});
		for(int i = 0; i < n; i++){
			sum[a[i].second] = a[i].first;
			for(pair<int, int> p : adj1[a[i].second]){
				adj[a[i].second].insert(p);
			}
		}
	}
	int get(int x){return v[x] < 0 ? x : v[x] = get(v[x]);}
	
	void unite(int x, int y, pair<int, int> val){
		x = get(x); y = get(y);
		while((int)adj[x].size() > 0 && *adj[x].begin() <= val) adj[x].erase(adj[x].begin());
		if(x == y) return;
		if(v[x] > v[y]) swap(x, y);
		v[x] += v[y]; v[y] = x;	sum[x] += sum[y];
		if(adj[x].size() < adj[y].size()) swap(adj[x], adj[y]);
		for(pair<int, int> p : adj[y]) adj[x].insert(p);
		while((int)adj[x].size() > 0 && *adj[x].begin() <= val) adj[x].erase(adj[x].begin());
	}
	
	ll calc(int i){
		i = get(i);
		if((int)adj[i].size() == 0) return sum[i];
		else if(sum[i] >= (*adj[i].begin()).first) return -(*adj[i].begin()).second;
		else return sum[i];
	}
};

void solve(){
	int n, m; cin >> n >> m;
	vector<pair<int, int>> v(n);
	ll total_sum = 0;
	for(int i = 0; i < n; i++){
		int x; cin >> x;
		total_sum += x;
		v[i] = {x, i};
	}
	vector<vector<pair<int, int>>> adj(n);
	for(int i = 0; i < m; i++){
		int a, b; cin >> a >> b; a--; b--;
		adj[a].push_back({v[b].first, b});
		adj[b].push_back({v[a].first, a});
	}
	vector<ll> ans(n);
	sort(v.begin(), v.end());
	DSU UF; UF.init(v, adj);
	for(int i = 0; i < n; i++){
		for(pair<int, int> p : adj[v[i].second]){
			if(p > v[i]) continue;
			UF.unite(v[i].second, p.second, v[i]);
		}
		ans[v[i].second] = UF.calc(v[i].second);
	}
	for(int j = n - 1; j >= 0; j--){
		int i = v[j].second;
		if(ans[i] <= 0) ans[i] = ans[-ans[i]];
	}
	for(int x : ans) cout << (x == total_sum ? 1 : 0);
	cout << endl;
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	solve();
}

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Incorrect 2 ms 724 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Incorrect 145 ms 46064 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 251 ms 44832 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 277 ms 46044 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Incorrect 2 ms 724 KB Output isn't correct
5 Halted 0 ms 0 KB -