oj.uz

답안 #877031

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
877031 2023-11-22T18:32:26 Z andrei_iorgulescu Stranded Far From Home (BOI22_island) C++14
10 / 100
 820 ms 154328 KB 
#include <bits/stdc++.h>

using namespace std;

#define int long long

struct grup
{
    vector<int>noduri_alive;
    int nr_oameni;
    multiset<pair<int,int>> edges;
};

int n,m,s[200005];
vector<pair<int,int>>G[200005];
int t[200005],sz[200005];
grup g[200005];
bool sol_finala[200005];

bool cmp(int x,int y)
{
    if (g[x].nr_oameni != g[y].nr_oameni)
        return g[x].nr_oameni < g[y].nr_oameni;
    return x < y;
}

multiset<int,decltype(cmp)*>st(cmp);

int ancestor(int nod)
{
    while (nod != t[nod])
        nod = t[nod];
    return nod;
}

void join(int x,int y)
{
    if (sz[x] < sz[y])
        swap(x,y);
    sz[x] += sz[y];
    t[y] = x;
    g[x].nr_oameni += g[y].nr_oameni;
    for (auto it : g[y].noduri_alive)
        g[x].noduri_alive.push_back(it);
    for (auto it : g[y].edges)
        g[x].edges.insert(it);
    g[y].nr_oameni = 0;
    g[y].noduri_alive.clear();
    g[y].edges.clear();
    st.insert(x);
}

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 >> s[i];
    for (int i = 1; i <= m; i++)
    {
        int x,y;
        cin >> x >> y;
        G[x].push_back({s[y],y});
        G[y].push_back({s[x],x});
    }
    for (int i = 1; i <= n; i++)
    {
        t[i] = i;
        sz[i] = 1;
        g[i].noduri_alive = {i};
        g[i].nr_oameni = s[i];
        for (auto it : G[i])
            g[i].edges.insert(it);
        st.insert(i);
    }
    while (st.size() >= 2)
    {
        /*for (auto it : st)
        {
            cout << it << ' ' << g[it].nr_oameni << endl;
            for (auto itt : g[it].noduri_alive)
                cout << itt << ' ';
            cout << endl;
            for (auto itt : g[it].edges)
                cout << itt.first << ' ' << itt.second << endl;
            cout << endl;
        }
        cout << endl;*/
        int nod = *st.begin();
        //cout << nod << endl;
        while (true)
        {
            pair<int,int>aux = *(g[nod].edges.begin());
            if (ancestor(aux.second) == nod)
                g[nod].edges.erase(aux);
            else
                break;
        }
        pair<int,int>aux = *(g[nod].edges.begin());
        //cout << aux.first << ' ' << aux.second << endl;
        g[nod].edges.erase(g[nod].edges.begin());
        if (aux.first > g[nod].nr_oameni)
        {
            //cout << "caz1 " << nod << endl;
            st.erase(nod);
            g[nod].noduri_alive.clear();
        }
        else
        {
            //cout << "caz2 " << nod << ' ';
            int x = aux.second;
            x = ancestor(x);
            //cout << x << endl;
            st.erase(st.find(nod));
            //cout << st.size() << endl;
            if (g[x].noduri_alive.size() != 0)
                st.erase(x);
            join(nod,x);
        }
    }
    for (auto it : st)
    {
        for (auto x : g[it].noduri_alive)
            sol_finala[x] = true;
    }
    for (int i = 1; i <= n; i++)
    {
        if (sol_finala[i] == false)
            cout << 0;
        else
            cout << 1;
    }
    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
**/

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 24924 KB Output is correct
2 Correct 4 ms 25020 KB Output is correct
3 Correct 4 ms 24924 KB Output is correct
4 Runtime error 27 ms 51464 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 24924 KB Output is correct
2 Correct 4 ms 25080 KB Output is correct
3 Correct 632 ms 85376 KB Output is correct
4 Correct 383 ms 78724 KB Output is correct
5 Correct 720 ms 81308 KB Output is correct
6 Correct 615 ms 82892 KB Output is correct
7 Correct 665 ms 83024 KB Output is correct
8 Correct 399 ms 78556 KB Output is correct
9 Correct 439 ms 82380 KB Output is correct
10 Correct 299 ms 75764 KB Output is correct
11 Correct 356 ms 79400 KB Output is correct
12 Correct 530 ms 78776 KB Output is correct
13 Correct 381 ms 78396 KB Output is correct
14 Correct 387 ms 78328 KB Output is correct
15 Correct 392 ms 80164 KB Output is correct
16 Correct 290 ms 77216 KB Output is correct

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 24924 KB Output is correct
2 Runtime error 820 ms 153488 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 24924 KB Output is correct
2 Runtime error 291 ms 154328 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 24924 KB Output is correct
2 Correct 4 ms 25020 KB Output is correct
3 Correct 4 ms 24924 KB Output is correct
4 Runtime error 27 ms 51464 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -