Submission #604096

#	Time	Username	Problem	Language	Result	Execution time	Memory
604096		l_reho	Stranded Far From Home (BOI22_island)	C++14	10 / 100	362 ms	30924 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<pair<ll, int>> A1;
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;
}
/*

5 4
40 15 50 31 31
1 2
2 3
3 4
4 5
 
 
*/
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);
	A1.assign(N, pair<ll, int>());
	
	P.assign(N, 0);
	
	graph.assign(N, vector<int>());
	vis.assign(N, false);
	
	for(int i = 0; i < N; i++){
		int v;
		cin>>v;
		A[i] = v;
		A1[i] = {v, i};
	}
	
	sort(A1.begin(), A1.end(), greater<pair<ll, int>>());
	
	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);
	
	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;
	}

	if(subtask3){
		vector<ll> pref_sum(N+1, 0);
		
		for(int i = 0; i < N; i++){
			pref_sum[i+1] += pref_sum[i] + A[i];
		}
		
		set<int> s;
		ans[A1[0].second] = 1;
		s.insert(A1[0].second);
		for(int i = 1; i < N; i++){
			int color = A1[i].second;
			// mi serve il primo abitante sulla sinistra già preso e 
			// il primo abitante sulla destra già preso cioè ans[i] = true;
			auto r = s.lower_bound(color);
			auto l = r;
			int r_idx = 0;
			int l_idx = 0;
			
			if(l == s.begin()){
				l_idx = -1;
			}else l_idx = *(--l);
			
			if(r == s.end()){
				r_idx = N;
			}else r_idx = *r;
			
			// cout<<"DEBUG-->"<<color<<" "<<l_idx<<" "<<r_idx<<endl;
			if(l_idx == -1)
				ans[color] = (pref_sum[r_idx] - pref_sum[l_idx+1]) >= A[r_idx];
			else if(r_idx == N)
				ans[color] = (pref_sum[r_idx] - pref_sum[l_idx+1]) >= A[l_idx];
			else ans[color] = (pref_sum[r_idx] - pref_sum[l_idx+1]) >= max(A[r_idx], A[l_idx]);
			
			if(ans[color])
				s.insert(color);
		}
		
		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