Submission #1122926

#	Time	Username	Problem	Language	Result	Execution time	Memory
1122926		adiyer	Stranded Far From Home (BOI22_island)	C++17	100 / 100	464 ms	45604 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 + 300;
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;
ll a[N], p[N], sum[N], ans[N], mx[N];

vll g[N];

set < ll > cmp[N];

vpll ord;

ll get(ll v){
    if(v == p[v]) return v;
    return p[v] = get(p[v]);
}

void unite(ll x, ll y){
    x = get(x), y = get(y);
    if(x == y) return;
    if(len(cmp[x]) < len(cmp[y])) swap(x, y);
    for(auto v : cmp[y]) cmp[x].insert(v);
    sum[x] += sum[y], p[y] = x;
    mx[x] = max(mx[x], mx[y]);
    cmp[y].clear();
}

void output(){
    cin >> n >> m;    
    for(ll i = 1; i <= n; i++) cin >> a[i];
    for(ll i = 1, u, v; i <= m; i++) cin >> u >> v, g[v].pb(u),g[u].pb(v);
    for(ll i = 1; i <= n; i++){
         ord.pb({a[i], i}); 
         sum[i] = mx[i] = a[i]; 
         p[i] = i; 
         cmp[i].insert(i); 
         ans[i] = 1;
    }
    sort(all(ord));
    for(auto [x, v] : ord){
        // cout << "inline: " << v << '\n';
        for(ll u : g[v]){
            u = get(u);
            // cout << u << ' ' << v << ' ' << a[u] << ' ' << a[v] << '\n';
            if(mx[u] > a[v] || u == get(v)) continue;
            if(sum[u] >= a[v]){
                unite(u, v);
            }
            else{
                for(auto it : cmp[u]) ans[it] = 0;// cout << it << '\n';
                cmp[u].clear();
                unite(u, v);
            }
        }
        // cout << '\n';
    }
    for(ll i = 1; i <= n; i++) cout << ans[i];
}

const bool cases = 0;

signed main(){
//  file("disrupt");
    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: 10 / 10
• Subtask 3: 15 / 15
• Subtask 4: 30 / 30
• Subtask 5: 35 / 35