oj.uz

Submission #604074

# Submission time Handle Problem Language Result Execution time Memory
604074 2022-07-24T17:09:30 Z l_reho Stranded Far From Home (BOI22_island) C++14
0 / 100
 473 ms 27868 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<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]){
					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
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 0 ms 212 KB Output is correct
4 Incorrect 3 ms 384 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 326 ms 27868 KB Output is correct
4 Correct 246 ms 25368 KB Output is correct
5 Correct 289 ms 15064 KB Output is correct
6 Correct 304 ms 15416 KB Output is correct
7 Correct 347 ms 15572 KB Output is correct
8 Correct 364 ms 15508 KB Output is correct
9 Correct 272 ms 15296 KB Output is correct
10 Correct 228 ms 16988 KB Output is correct
11 Correct 235 ms 16880 KB Output is correct
12 Correct 317 ms 15528 KB Output is correct
13 Incorrect 358 ms 15320 KB Output isn't correct
14 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 473 ms 15268 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 316 ms 17696 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 0 ms 212 KB Output is correct
4 Incorrect 3 ms 384 KB Output isn't correct
5 Halted 0 ms 0 KB -