| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 721090 | YENGOYAN | Stranded Far From Home (BOI22_island) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
/*
//\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\\
\\ //
// 271828___182845__904523__53602__ \\
\\ 87___47____13______52____66__24_ //
// 97___75____72______47____09___36 \\
\\ 999595_____74______96____69___67 //
// 62___77____24______07____66__30_ \\
\\ 35___35____47______59____45713__ //
// \\
\\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\//
*/
#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <cmath>
#include <climits>
#include <algorithm>
#include <random>
#include <queue>
#include <deque>
#include <iomanip>
#include <string>
#include <tuple>
#include <bitset>
#include <chrono>
#include <ctime>
#include <fstream>
#include <stack>
#include <cstdio>
#include <functional>
using namespace std;
using LL = long long;
const int N = 1e5 + 5;
const LL mod = 1e9 + 7, inf = 1e18;
vector<int> dx = { 1, 0, 0, -1, 1, 1, -1, -1 };
vector<int> dy = { 0, 1, -1, 0, 1, -1, 1, -1 };
void solve() {
int n, m; cin >> n >> m;
vector<int> s(n);
map<int, vector<int>> srt;
for(int i = 0; i < n; ++i){
cin >> s[i];
srt[s[i]].push_back(i);
}
vector<int> t = s;
sort(t.begin(), t.end());
vector<vector<int>> gp(n);
for(int i = 0; i < m; ++i){
int u, v; cin >> u >> v;
gp[--u].push_back(--v);
gp[v].push_back(u);
}
vector<LL> par(n), sz(n);
for(int i = 0; i < n; ++i){
par[i] = i;
sz[i] = s[i];
}
string ans(n, '1');
vector<int> vis(n, -1);
function<int(int)> check = [&](int u){
if(vis[u] != -1) return vis[u];
if(ans[u] == '0') return vis[u] = 0;
if(par[u] == u) return vis[u] = 1;
return vis[u] = check(par[u]);
};
function<LL(LL)> get = [&](LL u){
if(par[u] == u) return u;
vis = vector<in> (n, -1);
if(!check(u)) ans[u] = '0';
return par[u] = get(par[u]);
};
function<void(int u, int v)> unions = [&](int u, int v){
int a = get(u), b = get(v);
if(a == b) return;
par[b] = a;
sz[a] += sz[b];
};
for(auto x : srt){
vector<int> nodes = x.second;
int cnt = x.first;
for(int &u : nodes){
for(int &v : gp[u]){
if(s[v] <= s[u]){
int p = get(v);
if(sz[p] < cnt){
ans[p] = '0';
}
}
}
}
for(int &u : nodes) {
for(int &v : gp[u]){
if(s[v] <= s[u]){
unions(u, v);
}
}
}
}
vis = vector<int> (n, -1);
for(int i = 0; i < n; ++i){
cout << check(i);
}
cout << "\n";
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
// int t; cin >> t; while (t--)
solve();
}