oj.uz

Submission #972099

# Submission time Handle Problem Language Result Execution time Memory
972099 2024-04-30T05:14:08 Z Nare_2007 Stranded Far From Home (BOI22_island) C++17
0 / 100
 924 ms 524288 KB 
#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;
			}
		}
	}
	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.0

# Verdict Execution time Memory Grader output
1 Runtime error 388 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 9820 KB Output is correct
2 Correct 3 ms 9776 KB Output is correct
3 Incorrect 95 ms 26716 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 9824 KB Output is correct
2 Incorrect 81 ms 20856 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 9824 KB Output is correct
2 Runtime error 924 ms 524288 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Runtime error 388 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -