Submission #601602

#	Time	Username	Problem	Language	Result	Execution time	Memory
601602		CSQ31	Stranded Far From Home (BOI22_island)	C++17	10 / 100	270 ms	63328 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];
int main()
{
	owo
	int n,m;
	cin>>n>>m;
	for(int i=0;i<n;i++){
		cin>>s[i];
		par[i] = 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 x:adj[v]){
				x = find(x);
				if(vis[x])continue;
				vis[x] = 1;
				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() && !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];
	}
	//for(int i=0;i<n;i++)cout<<dp[i]<<" ";
	//cout<<'\n';
	vector<bool>good(n,0);
	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];
		//cout<<u<<" "<<val<<'\n';
		if(gr[u].empty())good[u] = 1;
		for(int p:gr[u]){
			//cout<<p<<" ";
			if(good[p] && val >= s[group[p][0]])good[u] = 1;
		}
		//cout<<'\n';
	}
	for(int i=0;i<n;i++)cout<<good[find(i)];
	
	
	
}

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