oj.uz

Submission #604061

# Submission time Handle Problem Language Result Execution time Memory
604061 2022-07-24T16:21:40 Z l_reho Stranded Far From Home (BOI22_island) C++14
10 / 100
 334 ms 45636 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];
		
	}
	
}

void solver(int curr, int p, vector<bool> &ans){
	vis[curr] = true;
	vector<int> adj = graph[curr];
	
	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 1 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 226 ms 476 KB Output is correct
5 Correct 214 ms 432 KB Output is correct
6 Correct 248 ms 476 KB Output is correct
7 Correct 215 ms 488 KB Output is correct
8 Correct 159 ms 468 KB Output is correct
9 Correct 261 ms 552 KB Output is correct
10 Correct 99 ms 668 KB Output is correct
11 Correct 92 ms 664 KB Output is correct
12 Correct 115 ms 424 KB Output is correct
13 Correct 186 ms 664 KB Output is correct
14 Correct 88 ms 432 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 Incorrect 303 ms 27240 KB Output isn't correct
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 Incorrect 321 ms 45636 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 334 ms 16956 KB Output isn't correct
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 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 226 ms 476 KB Output is correct
5 Correct 214 ms 432 KB Output is correct
6 Correct 248 ms 476 KB Output is correct
7 Correct 215 ms 488 KB Output is correct
8 Correct 159 ms 468 KB Output is correct
9 Correct 261 ms 552 KB Output is correct
10 Correct 99 ms 668 KB Output is correct
11 Correct 92 ms 664 KB Output is correct
12 Correct 115 ms 424 KB Output is correct
13 Correct 186 ms 664 KB Output is correct
14 Correct 88 ms 432 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Incorrect 303 ms 27240 KB Output isn't correct
18 Halted 0 ms 0 KB -