oj.uz

Submission #601686

# Submission time Handle Problem Language Result Execution time Memory
601686 2022-07-22T09:11:32 Z CSQ31 Stranded Far From Home (BOI22_island) C++17
10 / 100
 1000 ms 44852 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);
			}
		}
		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))continue;
		ll cur = s[i] * 1LL * sz(group[i]);
		set<array<ll,2>>S;
		S.insert({s[i],i});
		for(int j=0;j<n;j++)vis[j] = 0;
		while(!S.empty()){
			auto v = *S.begin();
			S.erase(v);
			vis[v[1]] = 1;
			if(v[1] != i){
				if(cur >= v[0])cur+=s[v[1]] * 1LL * sz(group[v[1]]);
				else break;
			}
			for(int x:anyy[v[1]])if(!vis[x])S.insert({s[x],x});
		}
		if(cur>=mx)good[i] = 1;
		
	}
	for(int i=0;i<n;i++)cout<<good[find(i)];
	
	
	
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23764 KB Output is correct
2 Correct 11 ms 23836 KB Output is correct
3 Correct 12 ms 23764 KB Output is correct
4 Correct 332 ms 24004 KB Output is correct
5 Correct 304 ms 24140 KB Output is correct
6 Correct 12 ms 23864 KB Output is correct
7 Correct 317 ms 24128 KB Output is correct
8 Correct 237 ms 23980 KB Output is correct
9 Correct 195 ms 24020 KB Output is correct
10 Correct 129 ms 24020 KB Output is correct
11 Correct 124 ms 24140 KB Output is correct
12 Correct 185 ms 23996 KB Output is correct
13 Correct 13 ms 23764 KB Output is correct
14 Correct 115 ms 23960 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23760 KB Output is correct
2 Correct 11 ms 23764 KB Output is correct
3 Execution timed out 1096 ms 44852 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23764 KB Output is correct
2 Execution timed out 1076 ms 42664 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23764 KB Output is correct
2 Execution timed out 1089 ms 41376 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23764 KB Output is correct
2 Correct 11 ms 23836 KB Output is correct
3 Correct 12 ms 23764 KB Output is correct
4 Correct 332 ms 24004 KB Output is correct
5 Correct 304 ms 24140 KB Output is correct
6 Correct 12 ms 23864 KB Output is correct
7 Correct 317 ms 24128 KB Output is correct
8 Correct 237 ms 23980 KB Output is correct
9 Correct 195 ms 24020 KB Output is correct
10 Correct 129 ms 24020 KB Output is correct
11 Correct 124 ms 24140 KB Output is correct
12 Correct 185 ms 23996 KB Output is correct
13 Correct 13 ms 23764 KB Output is correct
14 Correct 115 ms 23960 KB Output is correct
15 Correct 12 ms 23760 KB Output is correct
16 Correct 11 ms 23764 KB Output is correct
17 Execution timed out 1096 ms 44852 KB Time limit exceeded
18 Halted 0 ms 0 KB -