Submission #1050968

#TimeUsernameProblemLanguageResultExecution timeMemory
1050968sofijavelkovskaStranded Far From Home (BOI22_island)C++17
40 / 100
1098 ms21712 KiB
#include <bits/stdc++.h> using namespace std; const int MAXN=2e5, INF=2e9; int n, m; int a[MAXN]; vector<int> adj[MAXN]; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> n >> m; for (int i=0; i<n; i++) cin >> a[i]; for (int i=0; i<m; i++) { int x, y; cin >> x >> y; adj[x-1].push_back(y-1); adj[y-1].push_back(x-1); } set<int> values; for (int i=0; i<n; i++) values.insert(-a[i]); bool possible[n]={false}; queue<int> q; for (auto kt : values) { int k=-kt; bool visited[n]={false}; for (int i=0; i<n; i++) { if (a[i]!=k || visited[i]) continue; visited[i]=true; long long sum=a[i]; q.push(i); vector<int> nodes; nodes.push_back(i); int minsum=INF; while (!q.empty()) { int x=q.front(); q.pop(); for (auto y : adj[x]) { if (a[y]<=k && !visited[y]) { visited[y]=true; sum=sum+a[y]; q.push(y); if (a[y]==k) nodes.push_back(y); } if (a[y]>k && possible[y]) minsum=min(minsum, a[y]); } } if (minsum>sum && k!=-(*values.begin())) continue; for (auto x : nodes) possible[x]=true; } } for (int i=0; i<n; i++) cout << possible[i]; return 0; }
#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...