| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1121860 | adiyer | Stranded Far From Home (BOI22_island) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#pragma optimize ("g",on)
#pragma GCC optimize("inline")
#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("unroll-loops")
#pragma GCC optimize ("03")
#include <bits/stdc++.h>
#define file(s) freopen(s".in", "r", stdin); freopen(s".out", "w", stdout);
#define adiyer(); ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define bitcount(n) __builtin_popcountll(n)
#define ent (i == n ? '\n' : ' ')
#define all(x) x.begin(), x.end()
#define md ((l + r) >> 1)
#define rv(v) ((v << 1) | 1)
#define lv(v) (v << 1)
#define rs(v) rv(v), md + 1, r
#define ls(v) lv(v), l, md
#define len(s) (int) s.size()
#define pb push_back
#define S second
#define F first
// #define int long long
using namespace std;
typedef long long ll;
typedef long double ldb;
typedef vector < ll > vll;
typedef pair < ll, ll > pll;
typedef vector < pair < ll, ll > > vpll;
const int dx[8] = {1, 0, -1, 0, 1, 1, -1, -1};
const int dy[8] = {0, 1, 0, -1, -1, 1, -1, 1};
const int N = 2e5 + 11;
const int mod = 998244353;
const int mod2 = 1e9 + 7;
const ll inf = 1e18 + 10;
const double eps = 1e-9;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
ll n, m, cnt, sum;
ll a[N], ok[N], was[N], mx[N], st[N], was2[N];
vll g[N];
set < pair < ll, ll > > q;
void bfs(ll S){
queue < ll > qu;
was2[S] = 1, qu.push(S);
while(len(qu)){
ll s = qu.front();
qu.pop();
cnt = 0, q.clear(), st[s] = 1, was[s] = s, q.insert({0, s});
bool cur = 1;
for(ll u : g[s]){
if(a[u] < a[s] && mx[u] >= a[s] && !ok[u]){
ok[s] = 0, mx[s] = mx[u], cur = 0;
}
if(a[u] < a[s] && ok[u]){
ok[s] = 1, mx[s] = sum, cur = 0;
}
}
if(cur){
bool br = 0;
while(len(q)){
ll c = (q.begin() -> F), v = (q.begin() -> S);
if(cnt < c){ ok[s] = 0; break; }
if(ok[v]){ ok[s] = 1; break; }
cnt += a[v];
if(cnt >= a[pos]){
cnt = sum;
ok[s] = 1;
break;
}
q.erase(q.begin());
for(ll u : g[v]){
if(was[u] != s){
was[u] = s, q.insert({a[u], u});
if(cnt > a[u] && ok[u]{
ok[v] = 1, cnt = sum;
br = 1;
break;
}
}
}
if(br) break;
if(q.empty()){
ok[s] = 1;
}
}
mx[s] = cnt;
if(ok[s]) mx[s] = sum;
}
for(ll u : g[s])
if(!was2[u])
was2[u] = 1, qu.push(u);
}
}
void output(){
ll pos = 1;
cin >> n >> m;
for(ll i = 1; i <= n; i++) cin >> a[i], sum += a[i], pos = (a[pos] < a[i] ? i : pos);
for(ll i = 1; i <= m; i++){
ll u, v;
cin >> u >> v;
g[v].pb(u), g[u].pb(v);
}
bfs(pos);
for(ll i = 1; i <= n; i++) cout << ok[i];
}
const bool cases = 0;
signed main(){
// file("abbreviation");
adiyer();
int tt = 1;
if(cases) cin >> tt;
for(int i = 1; i <= tt; i++){
// cout << "Case " << i << ":\n";
output();
}
}