oj.uz

Submission #601676

# Submission time Handle Problem Language Result Execution time Memory
601676 2022-07-22T09:06:54 Z CSQ31 Stranded Far From Home (BOI22_island) C++17
10 / 100
 1000 ms 39704 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);
		anyy[a].pb(b);
		anyy[b].pb(a);
	}
	for(int i=0;i<n;i++){
		ll cur = s[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+=v[0];
				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[i];
	
	
	
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23892 KB Output is correct
2 Correct 12 ms 23820 KB Output is correct
3 Correct 13 ms 23764 KB Output is correct
4 Correct 356 ms 23972 KB Output is correct
5 Correct 307 ms 23964 KB Output is correct
6 Correct 517 ms 23932 KB Output is correct
7 Correct 307 ms 23972 KB Output is correct
8 Correct 272 ms 23840 KB Output is correct
9 Correct 552 ms 24080 KB Output is correct
10 Correct 137 ms 23904 KB Output is correct
11 Correct 156 ms 23988 KB Output is correct
12 Correct 206 ms 24068 KB Output is correct
13 Correct 307 ms 23924 KB Output is correct
14 Correct 179 ms 23960 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23764 KB Output is correct
2 Correct 12 ms 23832 KB Output is correct
3 Execution timed out 1008 ms 39704 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 23800 KB Output is correct
2 Execution timed out 1020 ms 37580 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

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

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23892 KB Output is correct
2 Correct 12 ms 23820 KB Output is correct
3 Correct 13 ms 23764 KB Output is correct
4 Correct 356 ms 23972 KB Output is correct
5 Correct 307 ms 23964 KB Output is correct
6 Correct 517 ms 23932 KB Output is correct
7 Correct 307 ms 23972 KB Output is correct
8 Correct 272 ms 23840 KB Output is correct
9 Correct 552 ms 24080 KB Output is correct
10 Correct 137 ms 23904 KB Output is correct
11 Correct 156 ms 23988 KB Output is correct
12 Correct 206 ms 24068 KB Output is correct
13 Correct 307 ms 23924 KB Output is correct
14 Correct 179 ms 23960 KB Output is correct
15 Correct 13 ms 23764 KB Output is correct
16 Correct 12 ms 23832 KB Output is correct
17 Execution timed out 1008 ms 39704 KB Time limit exceeded
18 Halted 0 ms 0 KB -