Submission #711057

#TimeUsernameProblemLanguageResultExecution timeMemory
711057blackscreen1Stranded Far From Home (BOI22_island)C++17
0 / 100
155 ms22020 KiB
#include <bits//stdc++.h> using namespace std; #define ll long long #define iloop(m, h) for (auto i = m; i != h; i+=(m<h?1:-1)) #define jloop(m, h) for (auto j = m; j != h; j+=(m<h?1:-1)) #define kloop(m, h) for (auto k = m; k != h; k+=(m<h?1:-1)) #define lloop(m, h) for (auto l = m; l != h; l+=(m<h?1:-1)) #define iloop_(m, h, g) for (auto i = m; i != h; i+=g) #define jloop_(m, h, g) for (auto j = m; j != h; j+=g) #define kloop_(m, h, g) for (auto k = m; k != h; k+=g) #define lloop_(m, h, g) for (auto l = m; l != h; l+=g) #define getchar_unlocked _getchar_nolock // comment before submission #define pll pair<ll,ll> #define plll pair<ll, pll> #define pllll pair<pll, pll> #define vll vector<ll> #define qll queue<ll> #define dll deque<ll> #define pqll priority_queue<ll> #define gll greater<ll> #define INF 1000000000000000 #define MOD1 1000000007 #define MOD2 998244353 #define MOD3 1000000009 mt19937 rng(chrono::system_clock::now().time_since_epoch().count()); ll par[200005], n, m; bool active[200005]; ll tot[200005], mi[200005]; ll a[200005]; pll b[200005]; vll adj[200005]; ll t1, t2; ll find(ll x) { return (par[x] == x ? x : par[x] = find(par[x])); } void merge(ll x, ll y) { x = find(x); y = find(y); //cout << x << " " << y << "\n"; if (x == y) return; if (tot[y] < mi[x] || tot[x] < mi[y]) return; //cout << "e\n"; tot[x] += tot[y]; mi[x] = min(mi[x], mi[y]); par[y] = x; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cin >> n >> m; iloop(0, n+1) { par[i] = i; } iloop(1, n+1) { cin >> a[i]; b[i] = {a[i], i}; tot[i] = mi[i] = a[i]; } iloop(0, m) { cin >> t1 >> t2; adj[t1].push_back(t2); adj[t2].push_back(t1); } sort(b+1, b+n+1); iloop(1, n+1) { //cout << b[i].second << "\n"; active[b[i].second] = 1; for (auto it : adj[b[i].second]) { if (active[it] && tot[find(it)] >= b[i].first) merge(b[i].second, it); } } iloop(1, n+1) { if (find(i) == find(b[n].second)) cout << 1; else cout << 0; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...