| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 601674 | CSQ31 | Stranded Far From Home (BOI22_island) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
//consider scc graph
//u -> v
//if u bad then v must be bad
//so every ingoing edge into v must be good and sum of sub(tree?graph?) must be >= minimal parent
//i dont even need scc,only scc is if all values are equal okay yes
#include <bits/stdc++.h>
using namespace std;
#define sz(a) (int)(a.size())
#define all(a) a.begin(),a.end()
#define pb push_back
#define owo ios_base::sync_with_stdio(0);cin.tie(0);
typedef long long int ll;
const int MAXN = 2e5+5;
int s[MAXN];
vector<int>adj[MAXN],group[MAXN],any[MAXN];
vector<int>gr[MAXN],g[MAXN],ord;
int vis[MAXN],par[MAXN],good[MAXN];
int find(int x){
if(x==par[x])return x;
return par[x] = find(par[x]);
}
void unite(int a,int b){
a = find(a);
b = find(b);
if(a==b)return;
par[a] = b;
}
void dfs(int v){
vis[v] = 1;
for(int x:g[v]){
if(!vis[x])dfs(x);
}
ord.pb(v);
}
ll dp[MAXN];
int main()
{
owo
int n,m,mx = 0;
cin>>n>>m;
for(int i=0;i<n;i++){
cin>>s[i];
par[i] = i;
mx = max(mx,s[i]);
}
for(int i=0;i<m;i++){
int a,b;
cin>>a>>b;
a--;
b--;
if(s[a] > s[b])adj[a].pb(b);
if(s[b] > s[a])adj[b].pb(a);
if(s[a]==s[b])unite(a,b);
any[a].pb(b);
any[b].pb(a);
}
for(int i=0;i<n;i++){
ll cur = s[i];
set<array<ll,2>>S;
S.insert({s[i],i});
for(int j=0;j<n;j++)vis[j] = 0;
while(!S.empty()){
auto v = *S.begin();
S.erase(v);
vis[v[1]] = 1;
if(v[1] != i){
if(cur >= v[0])cur+=v[0];
else break;
}
for(int x:any[v[1]])if(!vis[x])S.insert({s[x],x});
}
if(cur>=mx)good[i] = 1;
}
for(int i=0;i<n;i++)cout<<good[i];
}