#include <bits/stdc++.h> #define fi first #define se second #define FOR(i, a, b) for (int i = a, _b = b; i <= _b; ++i) #define FORD(i, a, b) for (int i = a, _b = b; i >= _b; --i) #define FORLL(i, a, b) for (ll i = a, _b = b; i <= _b; ++i) #define FORDLL(i, a, b) for (ll i = a, _b = b; i >= _b; --i) #define all(x) x.begin(), x.end() #define uni(x) sort(all(x)), x.erase(unique(all(x)), x.end()) using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<int, int> pii; typedef pair<ll, ll> pll; #define dbg(...) debug(#__VA_ARGS__, __VA_ARGS__) template<typename T> void __prine_one(const char *&s, const T &x) { while (*s == ' ') ++s; const char *p = s; int bal = 0; while (*s) { if (*s == '(') ++bal; else if (*s == ')') --bal; else if (*s == ',' && bal == 0) break; ++s; } cerr.write(p, s - p) << " = " << x; if (*s == ',') { cerr << " , "; ++s; } } template<typename... Args> void debug(const char *s, Args... args) { cerr << "[ "; int dummy[] = {0, (__prine_one(s, args), 0)...}; (void)dummy; cerr << " ]\n\n"; } // -------------------------------------------------------------------------------------------- const int maxn = 2e5 + 3; int n, m, a[maxn]; vector<int> g[maxn]; // -------------------------------------------------------------------------------------------- namespace sub1 { bool ans[maxn]; bool approve() { return true; } bool PFS(int src) { priority_queue<pii, vector<pii>, greater<pii>> Q; set<int> se; se.insert(src); ll total = a[src]; for (int u : g[src]) { Q.push({a[u], u}); se.insert(u); if (ans[u]) return true; } while (Q.size()) { int u = Q.top().se, val = Q.top().fi; Q.pop(); if (val > total) return false; total += val; for (int v : g[u]) if (!se.count(v)) { se.insert(v); if (ans[v]) return true; Q.push({a[v], v}); } } return true; } pii b[maxn]; void solve() { FOR(i, 1, n) { b[i] = {a[i], i}; } sort(b + 1, b + n + 1); FORD(i, n, 1) { ans[b[i].se] = PFS(b[i].se); } FOR(i, 1, n) cout << ans[i]; } } namespace sub2 { bool approve() { FOR(i, 2, n) if (a[i] > a[i - 1]) return false; FOR(i, 2, n) { int cnt = 0; for (int v : g[i]) cnt += i > v; if (cnt != 1) return false; } return true; } ll sum[maxn]; bool ans[maxn]; void dfs_pre(int u, int p) { sum[u] = a[u]; for (int v : g[u]) { if (v == p) continue; dfs_pre(v, u); sum[u] += sum[v]; } } void dfs_ans(int u, int p) { ans[u] = ans[p] && sum[u] >= a[p]; for (int v : g[u]) { if (v == p) continue; dfs_ans(v, u); } } void solve() { ans[1] = true; dfs_pre(1, -1); for (int u : g[1]) dfs_ans(u, 1); FOR(i, 1, n) cout << ans[i]; } } namespace sub3 { bool approve() { FOR(i, 1, n) { for (int v : g[i]) { if (abs(v - i) != 1) return false; } } return true; } ll pre[maxn]; int lg[maxn], f[maxn][20]; bool get_ans(int l) { int r = l; bool improve = true; ll total = a[l]; while (improve) { improve = false; // get_right { FORD(i, lg[n - r], 0) { if (r + (1 << i) <= n && f[r + 1][i] <= total) { total += pre[r + (1 << i)] - pre[r]; improve = true; r += 1 << i; } } } // get_left { FORD(i, lg[l - 1], 0) { if (l - (1 << i) >= 1 && f[l - (1 << i)][i] <= total) { total += pre[l - 1] - pre[l - (1 << i) - 1]; improve = true; l -= 1 << i; } } } } return r - l + 1 == n; } void solve() { FOR(i, 1, n) f[i][0] = a[i]; FOR(j, 1, 19) FOR(i, 1, n - (1 << j) + 1) f[i][j] = max(f[i][j - 1], f[i + (1 << j - 1)][j - 1]); FOR(i, 2, n) lg[i] = lg[i >> 1] + 1; FOR(i, 1, n) pre[i] = pre[i - 1] + a[i]; FOR(i, 1, n) { cout << get_ans(i); } } } void solve() { cin >> n >> m; FOR(i, 1, n) cin >> a[i]; FOR(i, 1, m) { int u, v; cin >> u >> v; if (u > v) swap(u, v); g[u].push_back(v); g[v].push_back(u); } if (sub3 :: approve()) return sub3 :: solve(), void(); if (sub2 :: approve()) return sub2 :: solve(), void(); if (sub1 :: approve()) return sub1 :: solve(), void(); } signed main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); #define TASK "TEST" if (fopen(TASK".INP", "r")) { freopen(TASK".INP", "r", stdin); freopen(TASK".OUT", "w", stdout); } solve(); return 0; }

island.cpp: In function 'int main()':
island.cpp:280:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  280 |         freopen(TASK".INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
island.cpp:281:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  281 |         freopen(TASK".OUT", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~