Submission #604190

#TimeUsernameProblemLanguageResultExecution timeMemory
604190DanerZeinStranded Far From Home (BOI22_island)C++14
0 / 100
265 ms16204 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef vector<int> vi; typedef pair<int,int> ii; const int MAX_N=2e5+10; vector<vi> G; int ha[MAX_N]; bool vis[MAX_N]; int n,m; void bfs(int u){ for(int i=0;i<n;i++) vis[i]=0; priority_queue<ii, vector<ii>, greater<ii> > q; vis[u]=1; ll co=ha[u]; for(auto &v:G[u]){ q.push(ii(ha[v],v)); } while(!q.empty()){ int x=q.top().second; q.pop(); if(co<ha[x]) continue; vis[x]=1; co+=ha[x]; for(auto &v:G[x]){ if(!vis[v]){ q.push(ii(ha[v],v)); } } } } int pa[MAX_N]; ll sb[MAX_N]; void dfs(int u,int p){ pa[u]=p; sb[u]=ha[u]; for(auto &v:G[u]){ if(v!=p){ dfs(v,u); sb[u]+=sb[v]; } } } ll sum[MAX_N]; bool habitant(int a,int b){ return ha[a]>ha[b]; } int main(){ cin>>n>>m; G.resize(n+1); for(int i=0;i<n;i++) cin>>ha[i]; for(int i=0;i<m;i++){ int a,b; cin>>a>>b; a--; b--; G[a].push_back(b); G[b].push_back(a); } string ans=""; ans.resize(n); sum[0]=ha[0]; for(int i=1;i<n;i++){ sum[i]=sum[i-1]+ha[i]; } vector<int> mah; for(int i=0;i<n;i++) mah.push_back(i); sort(mah.begin(),mah.end(),habitant); vector<int> lim; lim.push_back(-1); lim.push_back(mah[0]); lim.push_back(n); ans[mah[0]]='1'; for(int i=1;i<n;i++){ auto it=lower_bound(lim.begin(),lim.end(),mah[i]); int r=(*it); it--; int l=(*it); ll sr=sum[r-1]; ll sl=0; if(l!=-1) sl=sum[l]; ll s=sr-sl; int ml=0,mr=0; if(l!=-1) ml=ha[l]; if(r!=n) mr=ha[r]; if(l!=-1 && r!=n){ if(s>=ml) ans[mah[i]]=ans[l]; else{ if(s>=mr) ans[mah[i]]=ans[r]; else ans[mah[i]]='0'; } } else{ if(l==-1 && s>=mr) ans[mah[i]]=ans[r]; else if(r==n && s>=ml) ans[mah[i]]=ans[l]; else ans[mah[i]]='0'; } lim.push_back(mah[i]); } /*if(n>2000){ ans="1"; dfs(0,0); for(int i=1;i<n;i++){ if(sb[i]>=ha[pa[i]] && ans[pa[i]]=='1') ans+='1'; else ans+='0'; } } else{ for(int i=0;i<n;i++){ bfs(i); bool all=1; for(int j=0;j<n;j++) all&=vis[j]; if(all) ans+='1'; else ans+='0'; } }*/ cout<<ans<<endl; }
#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...