# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
601781 | JeanBombeur | Stranded Far From Home (BOI22_island) | C++17 | 381 ms | 524288 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
const int MAX_VILLAGE = (2e5);
vector <int> Adj[MAX_VILLAGE];
long long Size[MAX_VILLAGE];
pair <int, int> Sorted[MAX_VILLAGE];
bool Vu[MAX_VILLAGE];
long long Dsu[MAX_VILLAGE];
bool Valid[MAX_VILLAGE];
int nbVillages, nbRoads;
int Find(int a) {
if (Dsu[a] < 0)
return a;
int p = Find(Dsu[a]);
Valid[a] &= Valid[Dsu[a]];
return Dsu[a] = p;
}
void Union(int old, int big) {
old = Find(old);
if (- Dsu[old] < Size[big])
Valid[old] = false;
Dsu[big] = Dsu[old] - Size[big];
Dsu[old] = big;
return;
}
void Read() {
scanf("%d %d", &nbVillages, &nbRoads);
for (int i = 0; i < nbVillages; i ++)
{
Valid[i] = true;
scanf("%lld", &Size[i]);
Sorted[i] = {Size[i], i};
Dsu[i] = - Size[i];
}
sort(Sorted, Sorted + nbVillages);
for (int i = 0; i < nbRoads; i ++)
{
int a, b;
scanf("%d %d", &a, &b);
Adj[-- a].push_back(-- b);
Adj[b].push_back(a);
}
return;
}
void Solve() {
for (int i = 0; i < nbVillages; i ++)
{
int cur = Sorted[i].second;
Vu[cur] = true;
for (int dest : Adj[cur])
{
if (Vu[dest])
Union(dest, cur);
}
}
for (int i = 0; i < nbVillages; i ++)
{
printf("%c", Valid[i] ? '1' : '0');
}
printf("\n");
return;
}
int main() {
Read();
Solve();
return 0;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |