oj.uz

Submission #601602

# Submission time Handle Problem Language Result Execution time Memory
601602 2022-07-22T08:32:00 Z CSQ31 Stranded Far From Home (BOI22_island) C++17
10 / 100
 270 ms 63328 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];
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.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 19028 KB Output is correct
2 Correct 10 ms 19028 KB Output is correct
3 Correct 11 ms 19080 KB Output is correct
4 Incorrect 11 ms 19412 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 11 ms 19064 KB Output is correct
2 Correct 10 ms 19132 KB Output is correct
3 Correct 183 ms 53780 KB Output is correct
4 Correct 71 ms 22864 KB Output is correct
5 Correct 244 ms 48644 KB Output is correct
6 Correct 230 ms 49124 KB Output is correct
7 Correct 243 ms 49336 KB Output is correct
8 Correct 91 ms 22708 KB Output is correct
9 Correct 150 ms 47648 KB Output is correct
10 Correct 143 ms 43044 KB Output is correct
11 Correct 88 ms 23708 KB Output is correct
12 Correct 109 ms 26876 KB Output is correct
13 Correct 72 ms 22620 KB Output is correct
14 Correct 71 ms 22764 KB Output is correct
15 Correct 176 ms 63328 KB Output is correct
16 Correct 146 ms 62932 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 19028 KB Output is correct
2 Incorrect 190 ms 47584 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 19028 KB Output is correct
2 Incorrect 270 ms 45000 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 19028 KB Output is correct
2 Correct 10 ms 19028 KB Output is correct
3 Correct 11 ms 19080 KB Output is correct
4 Incorrect 11 ms 19412 KB Output isn't correct
5 Halted 0 ms 0 KB -