oj.uz

Submission #601620

# Submission time Handle Problem Language Result Execution time Memory
601620 2022-07-22T08:42:20 Z CSQ31 Stranded Far From Home (BOI22_island) C++17
10 / 100
 273 ms 63452 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,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;
				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];
	}
	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];
		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++)cout<<good[find(i)];
	
	
	
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 19028 KB Output is correct
2 Correct 12 ms 19028 KB Output is correct
3 Correct 9 ms 19028 KB Output is correct
4 Incorrect 13 ms 19304 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 9 ms 19028 KB Output is correct
2 Correct 9 ms 19028 KB Output is correct
3 Correct 234 ms 53924 KB Output is correct
4 Correct 86 ms 23060 KB Output is correct
5 Correct 273 ms 48740 KB Output is correct
6 Correct 236 ms 49232 KB Output is correct
7 Correct 259 ms 49616 KB Output is correct
8 Correct 93 ms 22820 KB Output is correct
9 Correct 155 ms 47792 KB Output is correct
10 Correct 179 ms 43256 KB Output is correct
11 Correct 92 ms 23880 KB Output is correct
12 Correct 102 ms 27056 KB Output is correct
13 Correct 76 ms 22620 KB Output is correct
14 Correct 84 ms 23000 KB Output is correct
15 Correct 171 ms 63452 KB Output is correct
16 Correct 132 ms 63020 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 19108 KB Output is correct
2 Incorrect 204 ms 47756 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 262 ms 45052 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 19028 KB Output is correct
2 Correct 12 ms 19028 KB Output is correct
3 Correct 9 ms 19028 KB Output is correct
4 Incorrect 13 ms 19304 KB Output isn't correct
5 Halted 0 ms 0 KB -