Submission #604029

#TimeUsernameProblemLanguageResultExecution timeMemory
604029l_rehoStranded Far From Home (BOI22_island)C++14
10 / 100
1098 ms13872 KiB
#include<bits/stdc++.h> using namespace std; #define ll long long struct info{ int node; ll people; bool operator <(const info &i) const{ return people > i.people; } }; int N, M; vector<ll> A; vector<bool> taken; vector<vector<int>> graph; void solve(){ cin>>N>>M; A.assign(N, 0); graph.assign(N, vector<int>()); for(ll &v:A) cin>>v; for(int i = 0; i < M; i++){ int a, b; cin>>a>>b; a--; b--; graph[a].push_back(b); graph[b].push_back(a); } vector<bool> ans(N, 1); ll sum = accumulate(A.begin(), A.end(), 0LL); for(int color = 0; color < N; color++){ priority_queue<info> pq; // inizializzo la pq vector<int> adj = graph[color]; taken.assign(N, false); taken[color] = true; for(int a : adj) pq.push({a, A[a]}); ll total = A[color]; int cnt = 1; while(!pq.empty()){ info i = pq.top(); pq.pop(); int node = i.node; ll abitants = i.people; if(taken[node]) continue; taken[node] = true; if(abitants > total) break; total += abitants; vector<int> adj = graph[node]; for(int a : adj){ if(taken[a]) continue; pq.push({a, A[a]}); } } ans[color] = total == sum; } for(int i = 0; i < N; i++) cout<<ans[i]; cout<<endl; } int main(){ solve(); return 0; }

Compilation message (stderr)

island.cpp: In function 'void solve()':
island.cpp:55:7: warning: unused variable 'cnt' [-Wunused-variable]
   55 |   int cnt = 1;
      |       ^~~
#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...