oj.uz

답안 #601691

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
601691 2022-07-22T09:14:53 Z CSQ31 Stranded Far From Home (BOI22_island) C++17
0 / 100
 383 ms 64804 KB 
//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],anyy[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);
	}
	for(int i=0;i<n;i++)group[find(i)].pb(i);
	for(int i=0;i<n;i++){
		if(i!=find(i))continue;
		for(int v:group[i]){
			for(int y:adj[v]){
				int x = find(y);
				if(vis[x] || x==i)continue;
				vis[x] = 1;
				anyy[i].pb(x);
				anyy[x].pb(i);
				g[i].pb(x);
				g[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(i==find(i) && !vis[i])dfs(i);
	
	for(int v:ord){
		dp[v] = sz(group[v]) * 1LL * s[v];
		for(int x:g[v])dp[v]+=dp[x];
	}
	vector<array<ll,2>>v;
	for(int i=0;i<n;i++)if(i == find(i))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]){
			if(good[p] && val >= s[p])good[u] = 1;
		}
	}
	for(int i=0;i<n;i++)cout<<good[find(i)];
	
	
	
}

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 23808 KB Output is correct
2 Correct 16 ms 23828 KB Output is correct
3 Correct 16 ms 23824 KB Output is correct
4 Incorrect 16 ms 24172 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 23716 KB Output is correct
2 Correct 17 ms 23764 KB Output is correct
3 Incorrect 278 ms 59620 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 23892 KB Output is correct
2 Incorrect 263 ms 64804 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 23764 KB Output is correct
2 Incorrect 383 ms 53836 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 23808 KB Output is correct
2 Correct 16 ms 23828 KB Output is correct
3 Correct 16 ms 23824 KB Output is correct
4 Incorrect 16 ms 24172 KB Output isn't correct
5 Halted 0 ms 0 KB -