Submission #722960

#TimeUsernameProblemLanguageResultExecution timeMemory
722960rshohruhStranded Far From Home (BOI22_island)C++14
0 / 100
1089 ms20568 KiB
#include <bits/stdc++.h> using namespace std; vector<vector<int> > g; vector<int> s; vector<bool> used; class Compare{ public: bool operator () (int a, int b){ return s[a] > s[b]; } }; priority_queue<int, vector<int>, Compare> b; int n; char bfs(int u){ used.assign(n+1, false); int cnt = s[u]; used[u] = true; for(int v: g[u]){ b.push(v); used[v] = true; } while(!b.empty()){ u = b.top(); b.pop(); if(s[u] > cnt) return '0'; cnt += s[u]; for(int v: g[u]){ if(!used[v]){ b.push(v); used[v] = true; } } } return '1'; } int main(){ int m; cin >> n >> m; s.resize(n+1); g.resize(n+1); for(int i = 1; i <= n; ++i) cin >> s[i]; for(int i = 0, u, v; i < m; ++i){ cin >> u >> v; g[u].push_back(v); g[v].push_back(u); } for(int i = 1; i <= n; ++i) cout << bfs(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...