Submission #572830

#TimeUsernameProblemLanguageResultExecution timeMemory
572830ritul_kr_singhStranded Far From Home (BOI22_island)C++17
25 / 100
213 ms33840 KiB
#include <bits/stdc++.h> using namespace std; #define int int64_t #define sp << ' ' << #define nl << '\n' const int LIM = 2e5; int N, M, s[LIM], e[LIM]; vector<int> g[LIM], h[LIM]; int find(int u) { return e[u] < 0 ? u : e[u] = find(e[u]); } signed main() { cin.tie(0)->sync_with_stdio(0); cin >> N >> M; array<int, 2> byS[N]; for(int i = 0; i < N; ++i) { cin >> s[i]; e[i] = -1; h[i] = {i}; byS[i] = {s[i], i}; } for(int i = 0; i < M; ++i) { int u, v; cin >> u >> v; --u, --v; if(make_pair(s[u], u) < make_pair(s[v], v)) swap(u, v); g[u].push_back(v); } sort(byS, byS + N); for(auto [_, r] : byS) { int u = find(r); for(int &v : g[r]) { v = find(v); if(s[v] < s[u]) h[v].clear(); if(size(h[v]) > size(h[u])) h[u].swap(h[v]); } for(int &v : g[r]) if(u != v) { for(int y : h[v]) h[u].push_back(y); s[u] += s[v]; e[v] = u; } } for(int u : h[find(0)]) s[u] = -1; for(int i = 0; i < N; ++i) cout << (s[i] < 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...