oj.uz

답안 #721425

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
721425 2023-04-10T21:34:34 Z gagik_2007 Stranded Far From Home (BOI22_island) C++17
10 / 100
 1000 ms 31940 KB 
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cmath>
#include <chrono>
#include <ctime>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <limits>
#include <iomanip>
#include <unordered_set>
#include <unordered_map>
#include <fstream>
#include <functional>
#include <random>
#include <cassert>
using namespace std;

typedef long long ll;
typedef long double ld;

#define ff first
#define ss second

ll ttt;
const ll INF = 1e18;
const ll MOD = 1e9 + 7;
const ll N = 200007;
const ll LG = 31;
ll n, m, k;
vector<ll>g[N];
ll a[N];
vector<ll>c[N];
ll p[N];
ll sz[N];
ll sum[N];
bool used[N];

void make_set(ll v) {
	p[v] = v;
	sz[v] = 1;
	sum[v] = a[v];
	c[v].push_back(v);
}

ll find_set(ll v) {
	if (p[v] == v)return v;
	return p[v] = find_set(p[v]);
}

void union_sets(ll v, ll u) {
	v = find_set(v);
	u = find_set(u);
	if (u != v) {
		if (sz[v] < sz[u]) {
			swap(v, u);
		}
		p[u] = v;
		sz[v] += sz[u];
		sum[v] += sum[u];
		sz[u] = 0;
		sum[u] = 0;
		if (c[v].size() < c[u].size()) {
			swap(c[v], c[u]);
		}
		for (ll x : c[u]) {
			c[v].push_back(x);
		}
		c[u].clear();
	}
}

priority_queue<pair<int, int>>deq;
bool used2[N];

string other_sol() {
	string ans = "";
	for (int u = 1; u <= n; u++) {
		for (int v = 1; v <= n; v++) {
			used2[v] = false;
		}
		while (!deq.empty()) {
			deq.pop();
		}
		for (int to : g[u]) {
			deq.push({ -a[to],to });
			used2[to] = true;
		}
		used2[u] = true;
		ll cur = a[u];
		bool ok = true;
		while (!deq.empty()) {
			int v = deq.top().ss;
			deq.pop();
			if (a[v] > cur) {
				ok = false;
				break;
			}
			cur += a[v];
			for (int to : g[v]) {
				if (!used2[to]) {
					deq.push({ -a[to],to });
					used2[to] = true;
				}
			}
		}
		ans += ok + '0';
	}
	return ans;
}

int main() {
	//freopen("in.txt", "r", stdin);
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m;
	vector<ll>vs;
	for (ll i = 1; i <= n; i++) {
		cin >> a[i];
		make_set(i);
		vs.push_back(i);
	}
	for (ll i = 0; i < m; i++) {
		ll x, y;
		cin >> x >> y;
		g[x].push_back(y);
		g[y].push_back(x);
	}
	cout << other_sol() << endl;
	return 0;
	auto comp = [](ll x, ll y) {
		return a[x] < a[y];
	};
	sort(vs.begin(), vs.end(), comp);
	ll i = 0;
	ll cur = a[vs[i]];
	//cout << "OK" << endl;
	while (i < n) {
		ll j = i;
		while (i < n && a[vs[i]] == cur) {
			for (ll to : g[vs[i]]) {
				if (a[to] <= cur) {
					union_sets(vs[i], to);
				}
			}
			//cout << i << endl;
			i++;
		}
		ll nxt = (i < n ? a[vs[i]] : 0);
		while (j < i) {
			cout << vs[j] << " " << sum[find_set(vs[j])] << endl;
			if (sum[find_set(vs[j])] < nxt) {
				//cout << vs[j] << endl;
				for (ll x : c[find_set(vs[j])]) {
					used[x] = true;
				}
				c[find_set(vs[j])].clear();
			}
			j++;
		}
		cur = nxt;
	}
	for (ll i = 1; i <= n; i++) {
		cout << !used[i];
	}
	cout << endl;
}

/// ---- - --------  ------ -------- -- - - -
/// Just a reminder. Ubuntu password is I O I
/// ---- - --------  ------ -------- -- - - -

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 9732 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 6 ms 9684 KB Output is correct
4 Correct 155 ms 9972 KB Output is correct
5 Correct 151 ms 9988 KB Output is correct
6 Correct 253 ms 9952 KB Output is correct
7 Correct 152 ms 9972 KB Output is correct
8 Correct 108 ms 9940 KB Output is correct
9 Correct 331 ms 9992 KB Output is correct
10 Correct 67 ms 10076 KB Output is correct
11 Correct 63 ms 9980 KB Output is correct
12 Correct 68 ms 10004 KB Output is correct
13 Correct 118 ms 9968 KB Output is correct
14 Correct 99 ms 9984 KB Output is correct

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Execution timed out 1059 ms 31940 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Execution timed out 1074 ms 30396 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Execution timed out 1058 ms 31456 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 9732 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 6 ms 9684 KB Output is correct
4 Correct 155 ms 9972 KB Output is correct
5 Correct 151 ms 9988 KB Output is correct
6 Correct 253 ms 9952 KB Output is correct
7 Correct 152 ms 9972 KB Output is correct
8 Correct 108 ms 9940 KB Output is correct
9 Correct 331 ms 9992 KB Output is correct
10 Correct 67 ms 10076 KB Output is correct
11 Correct 63 ms 9980 KB Output is correct
12 Correct 68 ms 10004 KB Output is correct
13 Correct 118 ms 9968 KB Output is correct
14 Correct 99 ms 9984 KB Output is correct
15 Correct 6 ms 9684 KB Output is correct
16 Correct 5 ms 9684 KB Output is correct
17 Execution timed out 1059 ms 31940 KB Time limit exceeded
18 Halted 0 ms 0 KB -