Submission #788831

#	Time	Username	Problem	Language	Result	Execution time	Memory
788831		Ozy	Stranded Far From Home (BOI22_island)	C++17	100 / 100	195 ms	41332 KiB

island

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define debug(a) cout << #a << " = " << a << endl
#define debugsl(a) cout << #a << " = " << a << ", "
#define rep(i,a,b) for(int i = (a); i<=(b); i++)
#define repa(i,a,b) for(int i = (a); i>=(b); i--)
#define pll pair<lli,lli>

#define MAX 200000
//para el vector de orden
#define id second

lli n,m,a,b,total;
lli arr[MAX+2],raiz[MAX+2],uf[MAX+2],sum[MAX+2],res[MAX+2];
vector<lli> aristas[MAX+2],n_arbol[MAX+2];
vector<pll> orden;

lli sube(lli pos) {
    //debugsl(pos);
    //debug(uf[pos]);

    if (uf[pos] == pos) return pos;
    uf[pos] = sube(uf[pos]);
    return uf[pos];
}

void dfs(lli pos) {
    res[pos] = 1;
    for(auto h : n_arbol[pos]) dfs(h);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> m;
    rep(i,1,n) {
        cin >> arr[i];
        orden.push_back({arr[i],i});
        uf[i] = i;
        sum[i] = arr[i];
        raiz[i] = 1;
        total += arr[i];
    }
    rep(i,1,m) {
        cin >> a >> b;
        aristas[a].push_back(b);
        aristas[b].push_back(a);
    }
    sort(orden.begin(), orden.end());

    //debug("llego");

    for(auto act : orden) {

        //debugsl(act.first);
        //debug(act.id);
        lli soy = sube(act.id);

        for(auto h : aristas[act.id]) {
            if (arr[h] > arr[act.id]) continue;

            //debug("llego");
            //debugsl(h);
            //debug(uf[1]);

            a = sube(h);
            if(a == soy) continue;

            if (sum[a] >= arr[act.id]) {
                n_arbol[soy].push_back(a);
                raiz[a] = 0;
            }
            sum[soy] += sum[a];
            uf[a] = soy;
        }

    }

    //debug("salgo");

    rep(i,1,n) {
        if (!raiz[i]) continue;
        if (sum[i] == total) dfs(i);
    }

    rep(i,1,n) cout << res[i];

    return 0;
}

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