oj.uz

Submission #601694

# Submission time Handle Problem Language Result Execution time Memory
601694 2022-07-22T09:15:36 Z CSQ31 Stranded Far From Home (BOI22_island) C++17
10 / 100
 415 ms 74488 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);
				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(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

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23736 KB Output is correct
2 Correct 16 ms 23748 KB Output is correct
3 Correct 16 ms 23840 KB Output is correct
4 Incorrect 18 ms 24160 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23708 KB Output is correct
2 Correct 15 ms 23764 KB Output is correct
3 Correct 288 ms 63868 KB Output is correct
4 Correct 106 ms 27736 KB Output is correct
5 Correct 410 ms 59372 KB Output is correct
6 Correct 415 ms 60328 KB Output is correct
7 Correct 413 ms 60676 KB Output is correct
8 Correct 158 ms 27672 KB Output is correct
9 Correct 283 ms 58936 KB Output is correct
10 Correct 287 ms 54992 KB Output is correct
11 Correct 129 ms 28656 KB Output is correct
12 Correct 162 ms 32540 KB Output is correct
13 Correct 85 ms 27244 KB Output is correct
14 Correct 118 ms 27688 KB Output is correct
15 Correct 297 ms 74488 KB Output is correct
16 Correct 219 ms 74028 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23812 KB Output is correct
2 Incorrect 288 ms 57548 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 23764 KB Output is correct
2 Incorrect 364 ms 54472 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23736 KB Output is correct
2 Correct 16 ms 23748 KB Output is correct
3 Correct 16 ms 23840 KB Output is correct
4 Incorrect 18 ms 24160 KB Output isn't correct
5 Halted 0 ms 0 KB -