Submission #948797

#TimeUsernameProblemLanguageResultExecution timeMemory
948797ifateenStranded Far From Home (BOI22_island)C++17
10 / 100
164 ms884 KiB
#include <bits/stdc++.h> using namespace std; #define int long long const int MAXN = 2003; vector<int> adj[MAXN]; int population[MAXN]; bool djikstra(int start) { priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq; pq.emplace(0, start); int have = population[start]; vector<bool> vis(MAXN); vis[start] = true; while (!pq.empty()) { auto [need, u] = pq.top(); pq.pop(); if (have >= need) have += need; else return false; for (auto& v : adj[u]) { if (vis[v]) continue; vis[v] = true; pq.emplace(population[v], v); } } return true; } signed main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin >> n >> m; for (int i = 1; i <= n; ++i) cin >> population[i]; for (int i = 1; i <= m; ++i) { int u, v; cin >> u >> v; adj[u].push_back(v); adj[v].push_back(u); } for (int i = 1; i <= n; ++i) cout << djikstra(i); }
#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...