oj.uz

Submission #604028

# Submission time Handle Problem Language Result Execution time Memory
604028 2022-07-24T15:39:25 Z l_reho Stranded Far From Home (BOI22_island) C++14
0 / 100
 1000 ms 13268 KB 
#include<bits/stdc++.h>
using namespace std;

#define ll long long

struct info{
	int node;
	ll people;
	
	bool operator <(const info &i) const{
		return people > i.people;
	}
	
};

int N, M;

vector<ll> A;
vector<bool> taken;
vector<vector<int>> graph;

void solve(){
	cin>>N>>M;
	
	A.assign(N, 0);
	graph.assign(N, vector<int>());
	
	for(ll &v:A) cin>>v;
	
	for(int i = 0; i < M; i++){
		int a, b;
		cin>>a>>b;
		a--;
		b--;
		graph[a].push_back(b);
		graph[b].push_back(a);
		
	}
	vector<bool> ans(N, 1);
	
	ll sum = accumulate(A.begin(), A.end(), 0LL);
	
	for(int color = 0; color < N; color++){
		priority_queue<info> pq;
		// inizializzo la pq
		vector<int> adj = graph[color];
		
		taken.assign(N, false);
		taken[color] = true;
		
		for(int a : adj)
			pq.push({a, A[a]});
		
		ll total = A[color];
		int cnt = 1;
		
		while(!pq.empty()){
			info i = pq.top();
			
			pq.pop();
			
			int node = i.node;
			ll abitants = i.people;
			
			if(taken[node]) continue;
			
			taken[node] = true;
			
			if(abitants > total)
				break;

			total += abitants;
			vector<int> adj = graph[node];
			cnt++;
			for(int a : adj){
				if(taken[a]) continue;
				pq.push({a, A[a]});
			}
			
		}	
		ans[color] = total == sum;
	}
	
	for(int i = 0; i < N; i++) cout<<ans[i]<<" ";
	cout<<endl;
	
}

int main(){
	solve();
	return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

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

Subtask #4
0 / 30.0

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

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -