Submission #666358

#	Time	Username	Problem	Language	Result	Execution time	Memory
666358		mychecksedad	Stranded Far From Home (BOI22_island)	C++17	100 / 100	234 ms	28368 KiB

island

/* Author : Mychecksdead */
#include<bits/stdc++.h>
using namespace std;
#define all(x) x.begin(), x.end()
#define pb push_back
const int N = 2e5 + 100;


int a[N], pos[N];
struct Dsu{
    vector<int> s, p, mx;
    vector<long long> sum;
    Dsu(int n){
        s.resize(n + 1, 1);
        p.resize(n + 1);
        mx.resize(n + 1);
        sum.resize(n + 1, 0ll);
        for(int i = 0; i <= n; ++i) p[i] = mx[i] = i;
        for(int i = 0; i <= n; ++i) sum[i] = a[i];
    }
    int find(int v){
        if(v==p[v]) return v;
        return (p[v]=find(p[v]));
    }
    void merge(int c, int b){
        c = find(c);
        b = find(b);
        if(c != b){
            if(s[c] > s[b]) swap(c, b);
            p[c] = b;
            s[b] += s[c];
            sum[b] += sum[c];
            mx[b] = pos[mx[c]] > pos[mx[b]] ? mx[c] : mx[b];
        }
    }
};


int n, m;
vector<int> g[N];
vector<bool> vis;
vector<int> ans;
pair<int, int> b[N];
int main(){
    cin.tie(0); ios::sync_with_stdio(0);
    cin >> n >> m;
    for(int i = 1; i <= n; ++i) cin >> a[i];
    for(int i = 1; i <= n; ++i) b[i] = {a[i], i};
    for(int i = 0; i < m; ++i){
        int a, b; cin >> a >> b;
        g[a].pb(b);
        g[b].pb(a);
    }


    Dsu d(n), M(n);
    sort(b + 1, b + 1 + n);
    ans.resize(n + 1, 0);
    vis.resize(n + 1, 0);

    for(int i = 1; i <= n; ++i) pos[b[i].second] = i;
    for(int i = 1; i <= n; ++i){
        int v = b[i].second;
        for(int u: g[v]){
            if(vis[u]){
                int co = d.find(u);
                if(d.sum[co] >= a[v]){
                    M.merge(v, d.mx[co]);
                }else{
                    ans[u] = -1;
                }
            }
        }
        for(int u: g[v]){
            if(vis[u]){
                d.merge(u, v);
            }
        }
        vis[v] = 1;
    }   
    vis.clear();
    vis.resize(n+1, 0);

    int co = M.find(b[n].second);

    for(int i = 1; i <= n; ++i) if(ans[i] != -1) ans[i] = (M.find(i) == co ? 1 : 0);


    for(int i = 1; i <= n; ++i) cout << (ans[i]==-1?0:ans[i]);

    return 0;
}

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