Submission #1079040

#TimeUsernameProblemLanguageResultExecution timeMemory
1079040LIFStranded Far From Home (BOI22_island)C++14
10 / 100
1092 ms12460 KiB
#include<bits/stdc++.h> using namespace std; int n,m; int head[500005]; int cnt = 0; long long int a[500005]; int last[500005]; long long int siz[500005]; set<pair<long long int,int>> s; struct edg { int to; int next; }edge[500005]; void add(int x,int y) { cnt++; edge[cnt].to = y; edge[cnt].next = head[x]; head[x] = cnt; } bool vis[500005]; int main() { cin>>n>>m; for(int i=1;i<=n;i++)cin>>a[i]; for(int i=1;i<=m;i++) { int x,y; cin>>x>>y; add(x,y); add(y,x); } for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++)vis[j] = false; s.clear(); vis[i] = true; // 以i開始,做bfs; int cnt = 0; pair<int,int> pp = make_pair(a[i],i); s.insert(pp); long long int nowval = 0; //cout<<"i "<<i<<endl; while(s.empty() == false) { auto it = (*s.begin()); int id = it.second; vis[id] = true; //cout<<"nowval: "<<nowval<<" "<<it.second<<endl; if(nowval >= it.first || it.second == i)nowval += it.first; else break; cnt++; s.erase(s.begin()); for(int j=head[id];j!=0;j=edge[j].next) { int to = edge[j].to; if(vis[to] == true)continue; pair<int,int> nw = make_pair(a[to],to); s.insert(nw); } } if(cnt >= n)last[i] = 1; } for(int i=1;i<=n;i++)cout<<last[i]; cout<<endl; 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...