oj.uz

Submission #601704

# Submission time Handle Problem Language Result Execution time Memory
601704 2022-07-22T09:19:04 Z CSQ31 Stranded Far From Home (BOI22_island) C++17
10 / 100
 414 ms 73412 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({-s[i],i});
	sort(all(v));
	for(auto x:v){
		int u = x[1];
		if(dp[u] >= mx)good[u] = 1;
		for(int p:gr[u]){
			if(good[p] && dp[u] >= 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 13 ms 23764 KB Output is correct
2 Correct 13 ms 23764 KB Output is correct
3 Correct 11 ms 23764 KB Output is correct
4 Incorrect 13 ms 24148 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 23764 KB Output is correct
2 Correct 11 ms 23796 KB Output is correct
3 Correct 191 ms 63916 KB Output is correct
4 Correct 74 ms 26716 KB Output is correct
5 Correct 317 ms 58460 KB Output is correct
6 Correct 248 ms 59220 KB Output is correct
7 Correct 276 ms 59476 KB Output is correct
8 Correct 84 ms 26516 KB Output is correct
9 Correct 184 ms 57784 KB Output is correct
10 Correct 208 ms 53852 KB Output is correct
11 Correct 83 ms 27584 KB Output is correct
12 Correct 99 ms 31356 KB Output is correct
13 Correct 69 ms 26536 KB Output is correct
14 Correct 84 ms 26512 KB Output is correct
15 Correct 229 ms 73412 KB Output is correct
16 Correct 159 ms 72860 KB Output is correct

Subtask #3
0 / 15.0

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

Subtask #4
0 / 30.0

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

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23764 KB Output is correct
2 Correct 13 ms 23764 KB Output is correct
3 Correct 11 ms 23764 KB Output is correct
4 Incorrect 13 ms 24148 KB Output isn't correct
5 Halted 0 ms 0 KB -