Submission #604077

#	Time	Username	Problem	Language	Result	Execution time	Memory
604077		l_reho	Stranded Far From Home (BOI22_island)	C++14	10 / 100	1090 ms	27836 KiB

island

#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<int> &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;
	bool subtask3 = true;
	
	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);
		
		subtask3 &= abs(a-b) == 1;
	}
	vector<int> ans(N, 2);
	
	
	ll sum = accumulate(A.begin(), A.end(), 0LL);
	
	bool subtask1 = (N <= 2000 && M <= 2000) || subtask3;
	
	if(subtask1){
		int last_color = N;
		
		for(int color = 0; color < last_color; color++){
			if(ans[color] != 2) continue;
			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];
			stack<int> nodes;
			
			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;
				
				if(ans[node] == 1){
					total = sum;
					break;
				}
					
				nodes.push(node);
				total += abitants;
				vector<int> adj = graph[node];

				for(int a : adj){
					if(taken[a]) continue;
					pq.push({a, A[a]});
				}
				
			}
			// se ans[color] è false, allora saranno false anche tutti quelli
			// che sono stati convinti durante il processo e quindi è inutile
			// ricalcolarli
			ans[color] = total == sum;
			if(!ans[color]){
				while(!nodes.empty()){
					ans[nodes.top()] = 0;
					nodes.pop();
				}
			}
		}
		
		for(int i = 0; i < N; i++) cout<<ans[i];
		cout<<endl;
		return;
	}

	dfs(0);

	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 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 15
• Subtask 4: 0 / 30
• Subtask 5: 0 / 35