Submission #877341

#	Time	Username	Problem	Language	Result	Execution time	Memory
877341		andrei_iorgulescu	Stranded Far From Home (BOI22_island)	C++14	100 / 100	177 ms	46544 KiB

island

#include <bits/stdc++.h>

using namespace std;

#define int long long

int n,m;
pair<int,int>a[200005];
vector<int>g[200005];

int t[200005],sz[200005];
vector<int>alive[200005];
int nroameni[200005];
int pos[200005];
bool solfinala[200005];

int tata(int x)
{
    if (x == t[x])
        return x;
    return tata(t[x]);
}

void joinlegit(int x,int y)
{
    if (sz[x] < sz[y])
        swap(x,y);
    t[y] = x;
    sz[x] += sz[y];
    nroameni[x] += nroameni[y];
    for (auto it : alive[y])
        alive[x].push_back(it);
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i].first;
        a[i].second = i;
        nroameni[i] = a[i].first;
    }
    for (int i = 1; i <= m; i++)
    {
        int x,y;
        cin >> x >> y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    sort(a + 1,a + n + 1);
    for (int i = 1; i <= n; i++)
        pos[a[i].second] = i;
    for (int i = 1; i <= n; i++)
    {
        t[i] = i;
        sz[i] = 1;
        alive[i].push_back(i);
    }
    for (int i = 2; i <= n; i++)
    {
        for (auto vecin : g[a[i].second])
        {
            if (pos[vecin] < pos[a[i].second])
            {
                if (tata(a[i].second) != tata(vecin))
                {
                    int x = tata(a[i].second),y = tata(vecin);
                    if (nroameni[y] >= a[i].first)
                        joinlegit(x,y);
                    else
                    {
                        alive[y].clear();
                        joinlegit(x,y);
                    }
                }
            }
        }
    }
    int pz = tata(pos[n]);
    for (auto it : alive[pz])
        solfinala[it] = true;
    for (int i = 1; i <= n; i++)
    {
        if (solfinala[i] == true)
            cout << 1;
        else
            cout << 0;
    }
    return 0;
}

/**
fiecare muchie devine defapt doua muchii, una x -> y cu cost s[y] si una y -> x cu cost s[x]

iau grupul cu macar un nod alive cu cei mai putini oameni si muchia lui spre un nod cu s cat mai mic
daca nu le pot conecta, marchez ca not alive toate nodurile alive din grup
daca le pot conecta, fac un small to large pe noduri (nu conteaza daca alive sau nu) pentru a le uni

ok, idee penala, acum ramane cum implementez

tin un dsu pentru grupuri, iar in tatal grupului tin:
-nodurile alive din grup
-cate alive am
-cati oameni am
-muchiile, sortate dupa cost

imi pot tine un set cu tatii grupurilor cu macar un nod alive, pentru fiecare retinand:
-ofc nodul tata
-numarul de oameni

o sa am ceva gen:

while (setul mai are >= 2 grupuri alive)
{
    iau si eu grupul din set cu numar minim de oameni
    lui ii iau muchia minima pentru care nu sunt ambele noduri conectate de muchie in grupul lui nod
    daca pe muchia asta nu pot conecta, atunci scot din set nodul nod (si atat)
    daca pe muchia asta pot conecta, am doua cazuri:
    1. nodul de care conectez nu e alive -> il scot pe asta din set, le dau join si bag combinata lor in set
    2. nodul de care conectez e alive -> ii scot pe ambii din set, le dau join si bag combinata lor in set
}

apoi, din grupul care mi-a mai ramas singur in set, afisez alea alive
de ce da RTE?????
**/


/**
sol2: sortez nodurile dupa valoare si le bag unul cate unul
cand bag un nod, vad ce muchii are cu ceva de pana acum si vad daca alea se pot lega de el sau doar el de ele
fuck, ce bou sunt, asta iese nlog penal
**/

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