#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int maxn = 2e5 + 1;
ll S[maxn];
vector <int> adj[maxn];
int state[maxn];
bool ans[maxn];
struct DSU {
vector <int> link, sz;
vector <ll> sum;
DSU (int s) {
link = sz = vector <int> (s+1);
sum = vector <ll> (s+1);
for (int i = 1; i <= s; i++) {
link[i] = i;
sz[i] = 1;
sum[i] = S[i];
}
}
int head(int x) {
while (x != link[x])
x = link[x];
return x;
}
bool same(int a, int b) {
return head(a) == head(b);
}
void unite(int a, int b) {
a = head(a);
b = head(b);
if (sz[a] > sz[b])
swap(a, b);
sz[a] += sz[b];
sum[a] += sum[b];
link[b] = a;
}
};
int main() {
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++)
cin >> S[i];
for (int i = 0; i < m; i++) {
int a, b;
cin >> a >> b;
adj[a].push_back(b);
adj[b].push_back(a);
}
DSU dsu(n+1);
vector <pair <int, int>> nodes;
for (int i = 1; i <= n; i++) {
nodes.push_back({S[i], i});
}
sort(nodes.begin(), nodes.end());
vector <int> nxt(n);
for (int i = n-1; i >= 0; i--) {
if (i+1 < n && nodes[i].first == nodes[i+1].first)
nxt[i] = nxt[i+1];
else if (i+1 < n)
nxt[i] = nodes[i+1].first;
}
for (int i = 0; i < n; i++) {
if (i > 0 && nodes[i-1].first == nodes[i].first)
continue;
vector <int> nodes2;
nodes2.push_back(nodes[i].second);
ll sum = nodes[i].first;
for (int j = i+1; j < n; j++) {
if (nodes[j].first != nodes[i].first)
break;
dsu.unite(nodes[j].second, nodes[i].second);
nodes2.push_back(nodes[j].second);
sum += nodes[j].first;
}
bool fine = false;
for (auto j : nodes2) {
for (auto k : adj[j]) {
if (sum >= S[k])
fine = true;
}
}
for (auto j : nodes2) {
if (fine)
state[j] = 1;
else
state[j] = -1;
}
}
for (int i = n-1; i >= 0; i--) {
if (i < n-1 && nodes[i+1].first == nodes[i].first)
continue;
if (state[nodes[i].second] == -1)
continue;
vector <int> nodes2;
nodes2.push_back(nodes[i].second);
for (int j = i-1; j >= 0; j--) {
if (nodes[j].first != nodes[i].first)
break;
nodes2.push_back(nodes[j].second);
}
bool fine = false;
if (i == n-1)
fine = true;
for (auto j : nodes2) {
for (auto k : adj[j]) {
fine |= ans[k];
}
}
for (auto j : nodes2)
ans[j] = fine;
}
for (int i = 1; i <= n; i++)
cout << ans[i];
cout << '\n';
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
4956 KB |
Output is correct |
| 2 |
Correct |
3 ms |
4956 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
4956 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
4956 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
4956 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
4952 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
5144 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
4956 KB |
Output is correct |
| 2 |
Correct |
3 ms |
4956 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
4956 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
