oj.uz

답안 #722983

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
722983 2023-04-13T06:46:27 Z Mardonbekhazratov Stranded Far From Home (BOI22_island) C++17
0 / 100
 1000 ms 13728 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(y==8) cout<<'\n'<<x<<'\n';
	//if(a[y]==3) cout<<'\n'<<x<<'\n';
	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];
		bool b=true;
		vis[i]=true;
		for(int z:v[i])
			if(!vis[z]) if(!dfs(z,i)){b=false;break;}
		cout<<(b?1:0);
	}
}

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 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

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Execution timed out 1074 ms 13728 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Execution timed out 1083 ms 13556 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Execution timed out 1067 ms 13616 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Incorrect 4 ms 340 KB Output isn't correct
5 Halted 0 ms 0 KB -