Submission #1121712

#	Time	Username	Problem	Language	Result	Execution time	Memory
1121712		vjudge1	Stranded Far From Home (BOI22_island)	C++17	10 / 100	1056 ms	42060 KiB

island

#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];

vll g[N];

set < pair < ll, ll > > q;

void dfs(ll s){
    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] && st[u] && !ok[u])
            cur = 0;
    for(ll u : g[s]){
        if(a[u] < a[s] && mx[u] >= a[s] && !ok[u]){
            cur = 0;
            mx[s] = mx[u];
        }
        if(a[u] < a[s] && ok[u]){
            ok[s] = 1, mx[s] = sum, cur = 0;
        }
        
    }
    if(cur){
        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];
            q.erase(q.begin());
            for(ll u : g[v])
                if(was[u] != s)
                    was[u] = s, q.insert({a[u], u});
            if(q.empty()){
                ok[s] = 1;
            }
        }
        mx[s] = cnt;
    }
    for(ll u : g[s])
        if(!st[u])
            dfs(u);
}
void output(){
	cin >> n >> m;
	for(ll i = 1; i <= n; i++) cin >> a[i], sum += a[i];
	for(ll i = 1; i <= m; i++){
		ll u, v;
		cin >> u >> v;
		g[v].pb(u), g[u].pb(v);
	}
    dfs(1);
    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();
    }
}

• Subtask 1: 10 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 15
• Subtask 4: 0 / 30
• Subtask 5: 0 / 35