Submission #1217364

#TimeUsernameProblemLanguageResultExecution timeMemory
1217364Ghulam_JunaidStranded Far From Home (BOI22_island)C++20
0 / 100
181 ms35644 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); const int N = 2e5 + 10; int n, m, a[N], sm[N], par[N]; vector<int> g[N], vals; vector<pair<int, pair<int, int>>> edges; set<int> alive[N]; int root(int v){ return (par[v] == -1 ? v : par[v] = root(par[v])); } void merge(int u, int v, int w){ if ((u = root(u)) == (v = root(v))) return ; if (sm[u] < w) alive[u].clear(); if (sm[v] < w) alive[v].clear(); if (alive[u].size() > alive[v].size()) swap(u, v); par[u] = v; sm[v] += sm[u]; for (int x : alive[u]) alive[v].insert(x); alive[u].clear(); } int main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> m; for (int i = 1; i <= n; i ++) cin >> a[i], vals.push_back(a[i]), par[i] = -1, sm[i] = a[i], alive[i].insert(i); for (int i = 0; i < m; i ++){ int u, v; cin >> u >> v; g[u].push_back(v); g[v].push_back(u); edges.push_back({max(a[u], a[v]), {u, v}}); } sort(edges.begin(), edges.end()); sort(vals.begin(), vals.end()); vals.resize(unique(vals.begin(), vals.end()) - vals.begin()); for (auto [w, E] : edges){ auto [u, v] = E; merge(u, v, w); } for (int v = 1; v <= n; v ++){ if (alive[root(v)].find(v) == alive[root(v)].end()) cout << '0'; else cout << '1'; } cout << endl; }
#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...