Submission #1121955

#	Time	Username	Problem	Language	Result	Execution time	Memory
1121955		adiyer	Stranded Far From Home (BOI22_island)	C++17	10 / 100	1086 ms	46764 KiB

island

#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, pos;
ll a[N], ok[N], was[N], mx[N], st[N], was2[N];
ll mxx[N][20];
 
vll g[N];
 
set < pair < ll, ll > > q;
 
ll get(ll l, ll r){
    ll k = __lg(r - l + 1);
    return max(mxx[l][k], mxx[r - (1 << k) + 1][k]);
}

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[s] = 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(){
	cin >> n >> m, pos = 1;
	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);
	}
    if(n <= 2e3){
        bfs(pos);
        for(ll i = 1; i <= n; i++) cout << ok[i];
    }
    else{
        ll pref[n + 3] = {};
        for(ll i = 1; i <= n; i++) pref[i] = pref[i - 1] + a[i]; 
        for(ll i = 1; i <= n; i++) mxx[i][0] = a[i];
        for(ll k = 1; k < 20; k++)
           for(ll i = 1; i + (1 << k) - 1 <= n; i++)
                mxx[i][k] = max(mxx[i][k - 1], mxx[i + (1 << (k - 1))][k - 1]);
        for(ll i = 1; i <= n; i++){
            ll cur = a[i], tr = i, tl = i, gd = 1;
            while(gd){
                ll l = i, r = n + 1;
                while(r - l > 1){
                    if(get(i + 1, md) > cur) r = md;
                    else l = md;
                }
                if(r != tr){
                    tr = r;
                    cur = pref[tr - 1] - pref[tl];
                    gd = 1;
                } 
                l = 0, r = i;
                while(r - l > 1){
                    if(get(md, i - 1) > cur) l = md;
                    else r = md;
                }
                if(l != tl){
                    tl = l;
                    cur = pref[tr - 1] - pref[tl];
                    gd = 1;
                }            
            }
            if(tl = 0 && tr == n + 1){
                cout << 1;
            }
            else{
                cout << 0;
            }
        }
    }
}
       
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();
    }
}

Compilation message (stderr)

island.cpp:1: warning: ignoring '#pragma optimize ' [-Wunknown-pragmas]
    1 | #pragma optimize ("g",on)
      | 
island.cpp: In function 'void output()':
island.cpp:154:19: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
  154 |             if(tl = 0 && tr == n + 1){
      |                ~~~^~~~~~~~~~~~~~~~~~

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