oj.uz

Submission #604029

# Submission time Handle Problem Language Result Execution time Memory
604029 2022-07-24T15:49:01 Z l_reho Stranded Far From Home (BOI22_island) C++14
10 / 100
 1000 ms 13872 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];

			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;
}

Compilation message

island.cpp: In function 'void solve()':
island.cpp:55:7: warning: unused variable 'cnt' [-Wunused-variable]
   55 |   int cnt = 1;
      |       ^~~

Subtask #1
10.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 0 ms 212 KB Output is correct
4 Correct 205 ms 400 KB Output is correct
5 Correct 183 ms 340 KB Output is correct
6 Correct 246 ms 400 KB Output is correct
7 Correct 204 ms 416 KB Output is correct
8 Correct 194 ms 388 KB Output is correct
9 Correct 238 ms 436 KB Output is correct
10 Correct 89 ms 396 KB Output is correct
11 Correct 93 ms 400 KB Output is correct
12 Correct 115 ms 400 KB Output is correct
13 Correct 164 ms 404 KB Output is correct
14 Correct 92 ms 408 KB Output is correct

Subtask #2
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 Execution timed out 1098 ms 13872 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 1092 ms 12784 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 1089 ms 13192 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 0 ms 212 KB Output is correct
4 Correct 205 ms 400 KB Output is correct
5 Correct 183 ms 340 KB Output is correct
6 Correct 246 ms 400 KB Output is correct
7 Correct 204 ms 416 KB Output is correct
8 Correct 194 ms 388 KB Output is correct
9 Correct 238 ms 436 KB Output is correct
10 Correct 89 ms 396 KB Output is correct
11 Correct 93 ms 400 KB Output is correct
12 Correct 115 ms 400 KB Output is correct
13 Correct 164 ms 404 KB Output is correct
14 Correct 92 ms 408 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Execution timed out 1098 ms 13872 KB Time limit exceeded
18 Halted 0 ms 0 KB -