Submission #972103

#	Time	Username	Problem	Language	Result	Execution time	Memory
972103		Nare_2007	Stranded Far From Home (BOI22_island)	C++17	0 / 100	903 ms	524288 KiB

island

#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <deque>
#include <iomanip>
#include <cstdio>
#include <string>
#define ll long long
using namespace std;
#define sort(a) sort(a.begin(), a.end())
#define reverse(a) reverse(a.begin(), a.end())
#define lli long long int 

vector<ll> g[200005];
ll dp[200005], a[200005];
vector<ll> ans(200005, 0);
bool vis[200005];

void dfs1(ll v, ll p) {
	if (g[v].size() == 1) {
		dp[v] = a[v];
		return;
	}
	for (auto x : g[v]) {
		if (x == p) {
			continue;
		}
		dfs1(x, v);
		dp[v] += dp[x];
	}
	dp[v] += a[v];
}

void solve() {
	ll n, m;
	cin >> n >> m;
	for (ll i = 1; i <= n; ++i) {
		cin >> a[i];
	}
	for (ll i = 0; i < m; ++i) {
		ll x, y;
		cin >> x >> y;
		g[x].push_back(y);
		g[y].push_back(x);
	}
	dfs1(1, 0);
	queue<ll> q;
	q.push(1);
	vis[1] = 1;
	ans[1] = 1;
	while (!q.empty()) {
		ll k = q.front();
		q.pop();
		for (auto x : g[k]) {
			if (!vis[x]) {
				vis[x] = 1;
				q.push(x);
				if (dp[x] >= a[k]) {
					ans[x] = 1;
					ans[k] = 1;
				}
			}
		}
	}
	for (ll i = 1; i <= n; ++i) {
		cout << ans[i];
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	ll t = 1;
	//cin >> t;
	while (t--) {
		solve();
	}
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 15
• Subtask 4: 0 / 30
• Subtask 5: 0 / 35