Submission #716042

#	Time	Username	Problem	Language	Result	Execution time	Memory
716042		MojoLake	Stranded Far From Home (BOI22_island)	C++17	0 / 100	330 ms	29912 KiB

island

#include <bits/stdc++.h>

#define debug(x) cout << #x << ": " << x << "\n"
#define all(x) x.begin(), x.end()

using namespace std;
using ll = long long;

const int N = 2e5 + 5;
const int inf = 1e9;
const ll LLinf = 1e16;

int siz[N], rep[N];
ll sum[N];
bool lose[N];
vector<int> child[N];

int id(int x){
    while(rep[x]!=x)x=rep[x];
    return x;
}

bool same(int a, int b){
    return id(a) == id(b);
}

void connect(int a, int b){
    a = id(a); b = id(b);
    if(siz[a] > siz[b])swap(a, b);
    siz[b] += siz[a];
    sum[b] += sum[a];
    rep[a] = b;
    child[b].push_back(a);
}

void init_uf(){
    for(int i = 1; i < N; ++i){
        siz[i] = 1;
        rep[i] = i;
    }
}

ll pop[N];
vector<int> g[N];
bool res[N], hand[N];

void update_res(int cur, bool f){
    f = f || lose[cur];
    res[cur] = f;
    hand[cur] = 1;

    for(int nex : child[cur]){
        update_res(nex, f);
    }
}

int main(){

    // if cannot get to any new ones:
    //      fail for this and its children
    // 
    // uf: size, sum, rep
    // kusee jos kaikki naapurit suurempii
    init_uf();
    int n, m;
    cin >> n >> m;
    vector<pair<ll, int>> v;
    for(int i = 1; i <= n; ++i){
        ll x; cin >> x;
        pop[i] = sum[i] = x;
        v.push_back({x, i});
    }
    sort(all(v));

    while(m--){
        int a, b;
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }

    for(auto [x, node] : v){
        vector<int> con;
        for(auto nex : g[node]){
            if(same(node, nex))continue;
            nex = id(nex);
            if(pop[node] > sum[nex]){
                lose[nex] = 1;
            }else if(pop[node] >= pop[nex]){
                con.push_back(nex);
            }
        }
        for(int nex : con)if(!same(node, nex))connect(node, nex);
    }

    for(int i = 1; i <= n; ++i){
        // cout << i << " " << id(i) << "\n";
        // cout << lose[i] << "\n";
        if(hand[id(i)])continue;
        // cout << "yea\n";
        update_res(id(i), 0);
    }
    for(int i = 1; i <= n; ++i){
        cout << !res[i];
    }
    cout << "\n";

    // 
}

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