Submission #1217348

#TimeUsernameProblemLanguageResultExecution timeMemory
1217348Ghulam_JunaidStranded Far From Home (BOI22_island)C++20
0 / 100
177 ms15376 KiB
#include <bits/stdc++.h> using namespace std; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); const int N = 2e5 + 10, Limit = 5e6; int n, m, a[N], iterations, val[N]; vector<int> g[N], seen; bool vis[N]; void process(int v){ int source = v; priority_queue<pair<int, int>> pq; int sm = a[v]; vis[v] = 1; seen.push_back(v); for (int u : g[v]){ iterations++; if (!vis[u]) pq.push({-a[u], u}); } while (!pq.empty() and !val[source]){ iterations++; auto [w, v] = pq.top(); pq.pop(); w = -w; if (w > sm) break; if (vis[v]) continue; if (val[v] == 1){ val[source] = 1; break; } sm += w; vis[v] = 1; seen.push_back(v); for (int u : g[v]){ iterations++; if (!vis[u]){ pq.push({-a[u], u}); if (a[u] <= sm and val[u] == 1) val[source] = 1; } } } } 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]; for (int i = 0; i < m; i ++){ int u, v; cin >> u >> v; g[u].push_back(v); g[v].push_back(u); } vector<int> vec; for (int i = 1; i <= n; i ++) vec.push_back(i); shuffle(vec.begin(), vec.end(), rng); for (int v : vec){ if (iterations > Limit) break; if (val[v]) continue; process(v); if (seen.size() == n or val[v] == 1) val[v] = 1; else{ for (int x : seen) val[v] = -1; } for (int x : seen) vis[x] = 0; seen.clear(); } for (int v = 1; v <= n; v ++){ if (val[v]) continue; process(v); } for (int v = 1; v <= n; v ++) cout << (val[v] == 1 ? '1' : '0'); 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...