제출 #601658

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
601658		CSQ31	Stranded Far From Home (BOI22_island)	C++17	0 / 100	1093 ms	45944 KiB

island

//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];
vector<int>gr[MAXN],g[MAXN],ord;
int vis[MAXN],par[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],sub[MAXN];
void get(int v,int root){
	dp[root]+=sub[v];
	for(int x:g[v])get(x,root);
	
}
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);
	}
	for(int i=0;i<n;i++)group[find(i)].pb(i);
	for(int i=0;i<n;i++){
		if(group[i].empty())continue;
		for(int v:group[i]){
			for(int y:adj[v]){
				int x = find(y);
				if(vis[x] || x==i)continue;
				vis[x] = 1;
				//cout<<i<<" "<<x<<'\n';
				g[i].pb(x);
				gr[x].pb(i);
			}
		}
		for(int v:group[i]){
			for(int x:adj[v]){
				vis[find(x)] = 0;
			}
		}
	}
	for(int i=0;i<n;i++)if(!group[i].empty())sub[i] = sz(group[i]) * 1LL * s[i];
	//for(int i=0;i<n;i++)get(i,i);
	vector<bool>good(n,0);
	/*
	for(int i=0;i<n;i++)cout<<sub[i]<<" ";
	cout<<'\n';
	for(int i=0;i<n;i++)cout<<dp[i]<<" ";
	cout<<'\n';
	* */
	/*
	for(int i=0;i<n;i++){
		if(!group[i].empty() && !vis[i])dfs(i);
	}
	for(int v:ord){
		dp[v] = sz(group[v]) * 1LL * s[group[v][0]];
		for(int x:g[v])dp[v]+=dp[x];
	}*/
	/*
	vector<array<ll,2>>v;
	for(int i=0;i<n;i++){
		if(!group[i].empty())v.pb({-dp[i],i});
	}
	sort(all(v));
	for(auto x:v){
		ll val = -x[0];
		int u = x[1];
		if(val >= mx)good[u] = 1;
		for(int p:gr[u]){
			//cout<<p<<" ";
			if(good[p] && val >= s[group[p][0]])good[u] = 1;
		}
	}*/
	for(int i=0;i<n;i++){
		if(group[i].empty())continue;
		for(int j=0;j<n;j++)vis[j] = 0;
		vis[i] = 1;
		ll cur = s[i];
		set<array<ll,2>>S;
		S.insert({s[i],i});
		while(!S.empty()){
			auto v = *S.begin();
			S.erase(v);
			vis[v[1]] = 1;
			if(v[1] == i)cur = sub[i];
			else if(cur >= v[0])cur+=sub[i];
			else break;
			for(int x:g[v[1]])if(!vis[x])S.insert({s[x],x});
			for(int x:gr[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[find(i)];
	
	
	
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 15
• Subtask 4: 0 / 30
• Subtask 5: 0 / 35