oj.uz

Submission #722900

# Submission time Handle Problem Language Result Execution time Memory
722900 2023-04-13T05:07:12 Z Mardonbekhazratov Stranded Far From Home (BOI22_island) C++17
0 / 100
 1000 ms 13824 KB 
#include<bits/stdc++.h>
using namespace std;
vector<vector<int>>v;
vector<int>a,res,dp;
vector<bool>vis;

bool cmp(int c,int b){return a[c]<a[b];}

bool dfs(int x,int y){
	vis[x]=true;
	if(dp[y]>=dp[x]) dp[y]+=dp[x];
	else return false;
	for(int z:v[x]){
		//cout<<z<<endl;
		if(!vis[z]) return dfs(z,y);
	}
	return true;
}

int main(){
	int n,m;cin>>n>>m;
	a.resize(n);res.assign(n,0);
	v.resize(n);dp.resize(n);
	for(int i=0;i<n;i++) cin>>a[i];
	for(int i=0;i<m;i++){
		int a,b;cin>>a>>b;--a,--b;
		v[a].push_back(b);
		v[b].push_back(a);
	}
	for(int i=0;i<n;i++) sort(v[i].begin(),v[i].end(),cmp);
	for(int i=0;i<n;i++){
		vis.assign(n,false);
		for(int i=0;i<n;i++) dp[i]=a[i];
		for(int z:v[i]){
			if(!vis[z]) if(!dfs(z,i)) break;
		}
		bool b=true;
		for(int j=0;j<n;j++){
			if(dp[i]>=dp[j]) continue;
			b=false;
			break;
		}cout<<(b?1:0);
	}
}

Subtask #1
0 / 10.0

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

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Execution timed out 1091 ms 13740 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Execution timed out 1062 ms 13692 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Execution timed out 1082 ms 13824 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

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