#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
using ll = long long;
using ii = pair<ll, ll>;
using vi = vector<int>;
#define pb push_back
#define pp pop_back
#define ff first
#define ss second
#define lb lower_bound
#define int ll
typedef tree<int, null_type, less<int>, rb_tree_tag,
tree_order_statistics_node_update> indexed_set;
int N, M, S[200001], tin[200001];
int timer, out[200001], st[800001];
bool reach[200001];
vector<int> adj[200001];
string res;
void update(int v, int l, int r, int p, int val) {
if(l == r) {
st[v] = val;
return;
}
int md = (l + r) / 2;
if(p <= md)
update(v * 2, l, md, p, val);
else update(v * 2 + 1, md + 1, r, p, val);
st[v] = st[v * 2] + st[v * 2 + 1];
}
int query(int v, int l, int r, int lo, int hi) {
if(l > hi || r < lo) return 0;
if(l >= lo && r <= hi) return st[v];
return query(v * 2, l, (l + r) / 2, lo, hi)
+ query(v * 2 + 1, (l + r) / 2 + 1, r, lo, hi);
}
void dfs(int v, int p) {
tin[v] = timer;
update(1, 0, N - 1, timer++, S[v]);
for(auto u : adj[v]) {
if(u == p) continue;
dfs(u, v);
}
out[v] = timer - 1;
}
void solve(int v, int p) {
int calc = query(1, 0, N - 1, tin[v], out[v]);
if(calc < S[p]) return;
reach[v] = reach[p]; res[v - 1] = '1';
for(auto u : adj[v]) {
if(u == p) continue;
solve(u, v);
}
}
void subtask2() {
dfs(1, 1); reach[1] = 1; solve(1, 1);
cout << res << "\n";
}
void subtask3() {
S[0] = S[N + 1] = 1e18; map<int, ii> DP; int Pr[200005]{0};
for(int l = 1; l <= N; l++)
Pr[l] = Pr[l - 1] + S[l];
for(int l = 1; l <= N; l++) {
int i = l - 1, j = l + 1, curr = S[l]; DP[l] = {l, l};
while(i >= 1 || j <= N) {
curr = Pr[j - 1] - Pr[i];
if(S[i] > curr && S[j] > curr) break;
if(S[i] <= curr) {
curr += S[i]; ii P = DP[i];
i = min(i - 1, P.ff);
j = max(j, P.ss);
}
if(S[j] <= curr) {
curr += S[j]; ii P = DP[j];
i = min(i, P.ff);
j = max(j + 1, P.ss);
}
}
DP[l] = {i, j};
if(i < 1 && j > N) res[l] = '1';
}
cout << res << "\n";
}
int32_t main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> N >> M; int R = 0; res.assign(N, '0');
for(int l = 1; l <= N; l++)
cin >> S[l], R += S[l];
bool can = 1;
for(int l = 0; l < M; l++) {
int U, V; cin >> U >> V;
adj[U].pb(V); adj[V].pb(U);
can &= (abs(U - V) == 1);
}
if(can) {
subtask3();
return 0;
}
bool ok = 1;
for(int l = 2; l <= N; l++) {
int v = 0;
for(auto U : adj[l])
v += (U < l);
ok &= (v == 1); ok &= (S[l] <= S[l - 1]);
}
if(ok) {
subtask2();
return 0;
}
for(int l = 1; l <= N; l++) {
int curr = 0;
priority_queue<ii, vector<ii>, greater<ii>> pq;
pq.push({0, l}); vector<bool> vis(N + 1, 0);
while(!pq.empty()) {
int A = pq.top().second, B = pq.top().first; pq.pop();
if(vis[A] || (S[A] > curr && A != l)) continue;
vis[A] = 1; curr += S[A];
for(auto E : adj[A]) {
if(vis[E]) continue;
pq.push({S[E], E});
}
}
if(curr == R) res[l - 1] = '1';
}
cout << res << "\n";
}
Compilation message
island.cpp: In function 'int32_t main()':
island.cpp:123:46: warning: unused variable 'B' [-Wunused-variable]
123 | int A = pq.top().second, B = pq.top().first; pq.pop();
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
4952 KB |
Output is correct |
| 2 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 3 |
Incorrect |
5 ms |
6484 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
5040 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
6484 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
6484 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
6484 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
4952 KB |
Output is correct |
| 2 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 3 |
Incorrect |
5 ms |
6484 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
