oj.uz

Submission #604068

# Submission time Handle Problem Language Result Execution time Memory
604068 2022-07-24T16:35:20 Z l_reho Stranded Far From Home (BOI22_island) C++14
20 / 100
 356 ms 45868 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, vis;
vector<vector<int>> graph;
vector<ll> P;

void dfs(int curr){
	vis[curr] = true;
	
	vector<int> adj = graph[curr];
	
	P[curr] = A[curr];
	
	for(int a : adj){
		if(vis[a]) continue;
		dfs(a);
		
		P[curr] += P[a];
		
	}
	
	
	// cout<<curr<<" "<<P[curr]<<endl;
}
/*

8 7
8 8 7 7 7 6 5 4
1 2
2 3
1 4
4 5
1 6
6 7
7 8
 
 
*/
void solver(int curr, int p, vector<bool> &ans){
	vis[curr] = true;
	vector<int> adj = graph[curr];
	
	if((int)adj.size() == 1 && curr){
		if(P[curr] >= A[p]){
			ans[curr] = 1;
		}else{
			ans[curr] = 0;
		}
		return;
	}
	
	for(int a : adj){
		if(vis[a]) continue;
		
		if(curr){
			if(P[curr] >= A[p]){
				ans[curr] = 1;
			}else{
				ans[curr] = 0;
				continue;
			}
		}
		
		solver(a, curr, ans);
		
	}
	
}

void solve(){
	cin>>N>>M;
	
	A.assign(N, 0);
	P.assign(N, 0);
	
	graph.assign(N, vector<int>());
	vis.assign(N, false);
	
	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);
	
	dfs(0);
	
	ll sum = accumulate(A.begin(), A.end(), 0LL);
	
	bool subtask1 = N <= 2000 && M <= 2000;
	
	if(subtask1){
		int last_color = N;
		
		for(int color = 0; color < last_color; 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];
			
			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;
		return;
	}

	vis.assign(N, false);
	ans.assign(N, false);
	
	ans[0] = 1;
	
	solver(0, -1, ans);
	
	for(int i = 0; i < N; i++) cout<<ans[i];
	cout<<endl;
	
}

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

Subtask #1
10.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 Correct 1 ms 212 KB Output is correct
4 Correct 212 ms 476 KB Output is correct
5 Correct 183 ms 468 KB Output is correct
6 Correct 260 ms 468 KB Output is correct
7 Correct 203 ms 476 KB Output is correct
8 Correct 157 ms 468 KB Output is correct
9 Correct 256 ms 556 KB Output is correct
10 Correct 87 ms 664 KB Output is correct
11 Correct 84 ms 668 KB Output is correct
12 Correct 105 ms 420 KB Output is correct
13 Correct 158 ms 664 KB Output is correct
14 Correct 93 ms 340 KB Output is correct

Subtask #2
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 297 ms 27084 KB Output is correct
4 Correct 237 ms 24576 KB Output is correct
5 Correct 289 ms 14284 KB Output is correct
6 Correct 307 ms 14836 KB Output is correct
7 Correct 335 ms 14804 KB Output is correct
8 Correct 321 ms 14860 KB Output is correct
9 Correct 356 ms 14540 KB Output is correct
10 Correct 223 ms 16172 KB Output is correct
11 Correct 220 ms 16256 KB Output is correct
12 Correct 277 ms 14812 KB Output is correct
13 Correct 252 ms 39756 KB Output is correct
14 Correct 229 ms 39604 KB Output is correct
15 Correct 348 ms 45868 KB Output is correct
16 Correct 236 ms 45432 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 318 ms 45656 KB Output isn't correct
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 Incorrect 332 ms 16988 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.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 Correct 1 ms 212 KB Output is correct
4 Correct 212 ms 476 KB Output is correct
5 Correct 183 ms 468 KB Output is correct
6 Correct 260 ms 468 KB Output is correct
7 Correct 203 ms 476 KB Output is correct
8 Correct 157 ms 468 KB Output is correct
9 Correct 256 ms 556 KB Output is correct
10 Correct 87 ms 664 KB Output is correct
11 Correct 84 ms 668 KB Output is correct
12 Correct 105 ms 420 KB Output is correct
13 Correct 158 ms 664 KB Output is correct
14 Correct 93 ms 340 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 297 ms 27084 KB Output is correct
18 Correct 237 ms 24576 KB Output is correct
19 Correct 289 ms 14284 KB Output is correct
20 Correct 307 ms 14836 KB Output is correct
21 Correct 335 ms 14804 KB Output is correct
22 Correct 321 ms 14860 KB Output is correct
23 Correct 356 ms 14540 KB Output is correct
24 Correct 223 ms 16172 KB Output is correct
25 Correct 220 ms 16256 KB Output is correct
26 Correct 277 ms 14812 KB Output is correct
27 Correct 252 ms 39756 KB Output is correct
28 Correct 229 ms 39604 KB Output is correct
29 Correct 348 ms 45868 KB Output is correct
30 Correct 236 ms 45432 KB Output is correct
31 Correct 0 ms 212 KB Output is correct
32 Incorrect 318 ms 45656 KB Output isn't correct
33 Halted 0 ms 0 KB -