#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
**/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
24924 KB |
Output is correct |
| 2 |
Correct |
4 ms |
25084 KB |
Output is correct |
| 3 |
Correct |
5 ms |
24924 KB |
Output is correct |
| 4 |
Runtime error |
25 ms |
51276 KB |
Execution killed with signal 11 |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
24924 KB |
Output is correct |
| 2 |
Correct |
5 ms |
25056 KB |
Output is correct |
| 3 |
Correct |
607 ms |
85340 KB |
Output is correct |
| 4 |
Correct |
370 ms |
81648 KB |
Output is correct |
| 5 |
Correct |
630 ms |
85436 KB |
Output is correct |
| 6 |
Correct |
630 ms |
87096 KB |
Output is correct |
| 7 |
Correct |
655 ms |
87724 KB |
Output is correct |
| 8 |
Correct |
426 ms |
83096 KB |
Output is correct |
| 9 |
Correct |
406 ms |
86836 KB |
Output is correct |
| 10 |
Correct |
298 ms |
79376 KB |
Output is correct |
| 11 |
Correct |
357 ms |
82868 KB |
Output is correct |
| 12 |
Correct |
505 ms |
81900 KB |
Output is correct |
| 13 |
Correct |
404 ms |
81092 KB |
Output is correct |
| 14 |
Correct |
370 ms |
81348 KB |
Output is correct |
| 15 |
Correct |
398 ms |
84860 KB |
Output is correct |
| 16 |
Correct |
279 ms |
80916 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
24920 KB |
Output is correct |
| 2 |
Runtime error |
778 ms |
153420 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
24924 KB |
Output is correct |
| 2 |
Runtime error |
279 ms |
154488 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
24924 KB |
Output is correct |
| 2 |
Correct |
4 ms |
25084 KB |
Output is correct |
| 3 |
Correct |
5 ms |
24924 KB |
Output is correct |
| 4 |
Runtime error |
25 ms |
51276 KB |
Execution killed with signal 11 |
| 5 |
Halted |
0 ms |
0 KB |
- |
