제출 #917666

#제출 시각아이디문제언어결과실행 시간메모리
917666themm1Stranded Far From Home (BOI22_island)C++17
0 / 100
210 ms40232 KiB
#include <bits/stdc++.h> using namespace std; // ordered set whith s.order_of_key(x) method, which returns rank of element x in set s /* #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace __gnu_pbds; typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set; */ // pair printing template <class T, class U> ostream& operator<<(ostream& out, const pair<T, U> &par) {out << "(" << par.first << "; " << par.second << ")"; return out;} // set printing template <class T> ostream& operator<<(ostream& out, const set<T> &cont) { out << "{"; for(const auto &x:cont) out << x << ", "; out << "}"; return out; } // map printing template <class T, class U> ostream& operator<<(ostream& out, const map<T, U> &cont) {out << "{"; for(const auto &x:cont) out << x << ", "; out << "}"; return out; } // unordered_set printing template <class T> ostream& operator<<(ostream& out, const unordered_set<T> &cont) {out << "{";for(const auto &x:cont) out << x << ", ";out << "}";return out;} // unordered_map printing template <class T, class U> ostream& operator<<(ostream& out, const unordered_map<T, U> &cont) {out << "{";for(const auto &x:cont) out << x << ", ";out << "}";return out;} // vector printing template<class T> ostream& operator<<(ostream& out, const vector<T> &cont){ out << "["; for (const auto &x:cont) out << x << ", "; out << "]"; return out;} #define print(x) cout << (x) << endl; #define dmp(x) cerr << #x << " = " << x << endl #define dmpn(x) cerr << #x << " = " << x << "; " #define dmpl(x) cerr << "Line " << __LINE__ << ": " << #x << " = " << x << endl #define int long long using ll = long long; using ld = long double; using pii = pair<int, int>; using pll = pair<ll, ll>; #define pb push_back #define ff first #define ss second #define all(x) begin(x), end(x) #define sz(x) (int)x.size() #define contains(s,x) ((s).find(x) != (s).end()) const int MOD = 998244353; int N, M; vector<vector<int>> g; vector<int> values; struct UnionFind { vector<int> heights, parents, sums; vector<vector<int>> possibles; UnionFind() { heights.assign(N, 1); parents.assign(N, -2); for (int i = 0; i < N; i++) { sums.pb(values[i]); possibles.pb({ i }); } } int find_(int v) { if (parents[v] == -1) return v; if (parents[v] == -2) return -1; return find_(parents[v]); } void union_(int u, int v, int merge_possibles) { int ru = find_(u), rv = find_(v); // adding v to u - root is u if (heights[ru] > heights[rv]) { parents[rv] = ru; sums[ru] += sums[rv]; if (merge_possibles) { if (sz(possibles[v]) > sz(possibles[u])) swap(possibles[u], possibles[v]); for (int x : possibles[v]) possibles[u].pb(x); // possibles for components should be always in root, which is u, but our possibles are in v } else { swap(possibles[u], possibles[v]); } // adding u to v - root is v } else { parents[ru] = rv; sums[rv] += sums[ru]; if (merge_possibles) { if (sz(possibles[u]) > sz(possibles[v])) swap(possibles[u], possibles[v]); for (int x : possibles[u]) possibles[v].pb(x); } } if (heights[ru] == heights[rv]) heights[rv]++; } }; void solve() { cin >> N >> M; g.assign(N, {}); values.assign(N, 0); vector<pii> sorted_vertices; for (int i = 0; i < N; i++) { cin >> values[i]; sorted_vertices.pb({ values[i], i }); } sort(all(sorted_vertices)); for (int i = 0; i < M; i++) { int u, v; cin >> u >> v; u--; v--; g[u].pb(v); g[v].pb(u); } UnionFind uf; for (pii pr : sorted_vertices) { int v = pr.ss; uf.parents[v] = -1; set<int> components; for (int u : g[v]) { int ru = uf.find_(u); if (ru != -1) components.insert(ru); } // dmpn(v); dmp(components); for (int comp : components) { bool merge_possibles = (uf.sums[comp] >= values[v]); // dmpn(comp); dmpn(uf.sums[comp]); dmp(values[v]); uf.union_(comp, v, merge_possibles); } } int root = uf.find_(0); set<int> final_possibles(all(uf.possibles[root])); for (int i = 0; i < N; i++) { if (contains(final_possibles, i)) cout << 1; else cout << 0; } cout << endl; } int32_t main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int t = 1; // cin >> t; while (t--) { solve(); } }
#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...