oj.uz

Submission #877341

# Submission time Handle Problem Language Result Execution time Memory
877341 2023-11-23T07:09:31 Z andrei_iorgulescu Stranded Far From Home (BOI22_island) C++14
100 / 100
 177 ms 46544 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16732 KB Output is correct
2 Correct 3 ms 16732 KB Output is correct
3 Correct 4 ms 16732 KB Output is correct
4 Correct 4 ms 16988 KB Output is correct
5 Correct 4 ms 16988 KB Output is correct
6 Correct 4 ms 16984 KB Output is correct
7 Correct 4 ms 16884 KB Output is correct
8 Correct 4 ms 16984 KB Output is correct
9 Correct 3 ms 16988 KB Output is correct
10 Correct 4 ms 16988 KB Output is correct
11 Correct 4 ms 17104 KB Output is correct
12 Correct 4 ms 16988 KB Output is correct
13 Correct 3 ms 16984 KB Output is correct
14 Correct 4 ms 16988 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16984 KB Output is correct
2 Correct 3 ms 16828 KB Output is correct
3 Correct 104 ms 39624 KB Output is correct
4 Correct 98 ms 37736 KB Output is correct
5 Correct 115 ms 42024 KB Output is correct
6 Correct 124 ms 42944 KB Output is correct
7 Correct 124 ms 42928 KB Output is correct
8 Correct 106 ms 39244 KB Output is correct
9 Correct 113 ms 46544 KB Output is correct
10 Correct 84 ms 37192 KB Output is correct
11 Correct 99 ms 39752 KB Output is correct
12 Correct 113 ms 38092 KB Output is correct
13 Correct 101 ms 36864 KB Output is correct
14 Correct 95 ms 36900 KB Output is correct
15 Correct 108 ms 38184 KB Output is correct
16 Correct 73 ms 37392 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16732 KB Output is correct
2 Correct 169 ms 43524 KB Output is correct
3 Correct 146 ms 43964 KB Output is correct
4 Correct 111 ms 38340 KB Output is correct
5 Correct 92 ms 36808 KB Output is correct
6 Correct 148 ms 43788 KB Output is correct
7 Correct 108 ms 38440 KB Output is correct
8 Correct 117 ms 38336 KB Output is correct
9 Correct 71 ms 37412 KB Output is correct
10 Correct 98 ms 36808 KB Output is correct
11 Correct 122 ms 37600 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16732 KB Output is correct
2 Correct 153 ms 40460 KB Output is correct
3 Correct 162 ms 41464 KB Output is correct
4 Correct 161 ms 43384 KB Output is correct
5 Correct 166 ms 45096 KB Output is correct
6 Correct 159 ms 41412 KB Output is correct
7 Correct 92 ms 40704 KB Output is correct
8 Correct 72 ms 37828 KB Output is correct
9 Correct 78 ms 31440 KB Output is correct
10 Correct 131 ms 44980 KB Output is correct
11 Correct 117 ms 37480 KB Output is correct

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16732 KB Output is correct
2 Correct 3 ms 16732 KB Output is correct
3 Correct 4 ms 16732 KB Output is correct
4 Correct 4 ms 16988 KB Output is correct
5 Correct 4 ms 16988 KB Output is correct
6 Correct 4 ms 16984 KB Output is correct
7 Correct 4 ms 16884 KB Output is correct
8 Correct 4 ms 16984 KB Output is correct
9 Correct 3 ms 16988 KB Output is correct
10 Correct 4 ms 16988 KB Output is correct
11 Correct 4 ms 17104 KB Output is correct
12 Correct 4 ms 16988 KB Output is correct
13 Correct 3 ms 16984 KB Output is correct
14 Correct 4 ms 16988 KB Output is correct
15 Correct 3 ms 16984 KB Output is correct
16 Correct 3 ms 16828 KB Output is correct
17 Correct 104 ms 39624 KB Output is correct
18 Correct 98 ms 37736 KB Output is correct
19 Correct 115 ms 42024 KB Output is correct
20 Correct 124 ms 42944 KB Output is correct
21 Correct 124 ms 42928 KB Output is correct
22 Correct 106 ms 39244 KB Output is correct
23 Correct 113 ms 46544 KB Output is correct
24 Correct 84 ms 37192 KB Output is correct
25 Correct 99 ms 39752 KB Output is correct
26 Correct 113 ms 38092 KB Output is correct
27 Correct 101 ms 36864 KB Output is correct
28 Correct 95 ms 36900 KB Output is correct
29 Correct 108 ms 38184 KB Output is correct
30 Correct 73 ms 37392 KB Output is correct
31 Correct 3 ms 16732 KB Output is correct
32 Correct 169 ms 43524 KB Output is correct
33 Correct 146 ms 43964 KB Output is correct
34 Correct 111 ms 38340 KB Output is correct
35 Correct 92 ms 36808 KB Output is correct
36 Correct 148 ms 43788 KB Output is correct
37 Correct 108 ms 38440 KB Output is correct
38 Correct 117 ms 38336 KB Output is correct
39 Correct 71 ms 37412 KB Output is correct
40 Correct 98 ms 36808 KB Output is correct
41 Correct 122 ms 37600 KB Output is correct
42 Correct 3 ms 16732 KB Output is correct
43 Correct 153 ms 40460 KB Output is correct
44 Correct 162 ms 41464 KB Output is correct
45 Correct 161 ms 43384 KB Output is correct
46 Correct 166 ms 45096 KB Output is correct
47 Correct 159 ms 41412 KB Output is correct
48 Correct 92 ms 40704 KB Output is correct
49 Correct 72 ms 37828 KB Output is correct
50 Correct 78 ms 31440 KB Output is correct
51 Correct 131 ms 44980 KB Output is correct
52 Correct 117 ms 37480 KB Output is correct
53 Correct 3 ms 16732 KB Output is correct
54 Correct 3 ms 16876 KB Output is correct
55 Correct 3 ms 16732 KB Output is correct
56 Correct 4 ms 16888 KB Output is correct
57 Correct 4 ms 16884 KB Output is correct
58 Correct 4 ms 16988 KB Output is correct
59 Correct 4 ms 16988 KB Output is correct
60 Correct 3 ms 16988 KB Output is correct
61 Correct 3 ms 16988 KB Output is correct
62 Correct 4 ms 17052 KB Output is correct
63 Correct 4 ms 16988 KB Output is correct
64 Correct 4 ms 16988 KB Output is correct
65 Correct 4 ms 16988 KB Output is correct
66 Correct 4 ms 16988 KB Output is correct
67 Correct 100 ms 39704 KB Output is correct
68 Correct 98 ms 37836 KB Output is correct
69 Correct 117 ms 41920 KB Output is correct
70 Correct 133 ms 42976 KB Output is correct
71 Correct 121 ms 43004 KB Output is correct
72 Correct 108 ms 39112 KB Output is correct
73 Correct 114 ms 46536 KB Output is correct
74 Correct 80 ms 36896 KB Output is correct
75 Correct 98 ms 39616 KB Output is correct
76 Correct 110 ms 38184 KB Output is correct
77 Correct 86 ms 36760 KB Output is correct
78 Correct 112 ms 37120 KB Output is correct
79 Correct 95 ms 38340 KB Output is correct
80 Correct 72 ms 37316 KB Output is correct
81 Correct 156 ms 43700 KB Output is correct
82 Correct 148 ms 43892 KB Output is correct
83 Correct 107 ms 38344 KB Output is correct
84 Correct 96 ms 36968 KB Output is correct
85 Correct 147 ms 43736 KB Output is correct
86 Correct 106 ms 38352 KB Output is correct
87 Correct 110 ms 38404 KB Output is correct
88 Correct 94 ms 36700 KB Output is correct
89 Correct 116 ms 37596 KB Output is correct
90 Correct 176 ms 40372 KB Output is correct
91 Correct 154 ms 41280 KB Output is correct
92 Correct 166 ms 43212 KB Output is correct
93 Correct 177 ms 45332 KB Output is correct
94 Correct 132 ms 41416 KB Output is correct
95 Correct 93 ms 40776 KB Output is correct
96 Correct 77 ms 37824 KB Output is correct
97 Correct 78 ms 31368 KB Output is correct
98 Correct 129 ms 45116 KB Output is correct
99 Correct 122 ms 37340 KB Output is correct
100 Correct 33 ms 23324 KB Output is correct
101 Correct 168 ms 41920 KB Output is correct
102 Correct 115 ms 37572 KB Output is correct
103 Correct 127 ms 36620 KB Output is correct
104 Correct 165 ms 39796 KB Output is correct