This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int maxn = 2e5 + 1;
ll S[maxn];
vector <int> adj[maxn];
vector <int> mark[maxn];
bool ans[maxn];
bool inserted[maxn], vis[maxn], in_marked[maxn];
int id[maxn];
struct DSU {
vector <int> link, sz, lst_added;
vector <ll> sum;
DSU (int s) {
lst_added = link = sz = vector <int> (s+1);
sum = vector <ll> (s+1);
for (int i = 1; i <= s; i++) {
lst_added[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 (a == b)
return;
if (sz[a] > sz[b])
swap(a, b);
sz[a] += sz[b];
sum[a] += sum[b];
link[b] = a;
if (id[lst_added[a]] > id[lst_added[b]])
lst_added[a] = lst_added[a];
else
lst_added[a] = lst_added[b];
}
};
void dfs(int s, bool x) {
ans[s] &= x;
for (auto i : mark[s])
dfs(i, ans[s]);
}
int main() {
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
int n, m;
cin >> n >> m;
fill(ans, ans + n + 1, true);
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());
for (int i = 0; i < n; i++)
id[nodes[i].second] = i;
for (int i = 0; i < n; i++) {
for (auto j : adj[nodes[i].second]) {
if (!vis[j])
continue;
int x = dsu.lst_added[dsu.head(j)];
if (dsu.sum[dsu.head(j)] < nodes[i].first)
ans[x] = false;
if (!in_marked[x] && i != x) {
in_marked[x] = true;
mark[nodes[i].second].push_back(x);
}
dsu.unite(nodes[i].second, j);
}
vis[nodes[i].second] = true;
}
dfs(nodes[n-1].second, true);
for (int i = 1; i <= n; i++)
cout << ans[i];
cout << '\n';
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |