Submission #580078

#	Time	Username	Problem	Language	Result	Execution time	Memory
580078		wiwiho	Stranded Far From Home (BOI22_island)	C++14	100 / 100	195 ms	27992 KiB

island

#include <bits/stdc++.h>

#define iter(a) a.begin(), a.end()
#define lsort(a) sort(iter(a))
#define gsort(a) sort(iter(a), greater<>())
#define eb emplace_back
#define ef emplace_front
#define pob pop_back()
#define pof pop_front()
#define mp make_pair
#define F first
#define S second
#define uni(a) a.resize(unique(iter(a)) - a.begin())
#define printv(a, b) { \
    for(auto pv : a) b << pv << " "; \
    b << "\n"; \
}

using namespace std;

typedef long long ll;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

template<typename A, typename B>
ostream& operator<<(ostream& o, pair<A, B> p){
    return o << '(' << p.F << ',' << p.S << ')';
}

int n, m;
vector<int> dsu;
vector<int> id;
vector<ll> sum;
vector<vector<int>> g;
vector<bool> no;
int ts;
vector<bool> ans;

void init(){
    dsu.resize(n + 1);
    iota(iter(dsu), 0);
    id.resize(n + 1);
    iota(iter(id), 0);
    g.resize(2 * n + 1);
    no.resize(2 * n + 1);
    sum.resize(n + 1);
    ans.resize(n + 1);
    ts = n;
}

int findDSU(int a){
    if(dsu[a] != a) dsu[a] = findDSU(dsu[a]);
    return dsu[a];
}

int unionDSU(int a, int b){
    a = findDSU(a);
    b = findDSU(b);
    assert(a != b);
    dsu[b] = a;
    sum[a] += sum[b];
    return id[a] = ++ts;
}

void dfs(int now, bool t){
    if(no[now]) t = false;
    if(now <= n) ans[now] = t;
    for(int i : g[now]){
        dfs(i, t);
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    cin >> n >> m;
    init();

    vector<int> s(n + 1);
    for(int i = 1; i <= n; i++){
        cin >> s[i];
        sum[i] = s[i];
    }
    
    vector<pii> e;
    for(int i = 0; i < m; i++){
        int u, v;
        cin >> u >> v;
        if(s[u] < s[v]) swap(u, v);
        e.eb(mp(u, v));
    }
    sort(iter(e), [&](pii x, pii y){ return s[x.F] < s[y.F]; });

    for(pii i : e){
        int u, v;
        tie(u, v) = i;
        if(findDSU(u) == findDSU(v)) continue;
        
        v = findDSU(v);
        if(sum[v] < s[u]) no[id[v]] = true;
        u = findDSU(u);
        int t1 = id[u], t2 = id[v];
        int p = unionDSU(u, v);
        g[p].eb(t1);
        g[p].eb(t2);
    }
    
    int rt = id[findDSU(1)];
    dfs(rt, true);

    for(int i = 1; i <= n; i++) cout << ans[i];
    cout << "\n";

    return 0;
}

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