oj.uz

Submission #604077

# Submission time Handle Problem Language Result Execution time Memory
604077 2022-07-24T17:12:33 Z l_reho Stranded Far From Home (BOI22_island) C++14
10 / 100
 1000 ms 27836 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] == 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.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 5 ms 340 KB Output is correct
5 Correct 4 ms 404 KB Output is correct
6 Correct 4 ms 340 KB Output is correct
7 Correct 6 ms 340 KB Output is correct
8 Correct 3 ms 340 KB Output is correct
9 Correct 2 ms 468 KB Output is correct
10 Correct 3 ms 428 KB Output is correct
11 Correct 4 ms 340 KB Output is correct
12 Correct 4 ms 340 KB Output is correct
13 Correct 4 ms 340 KB Output is correct
14 Correct 8 ms 452 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 1 ms 212 KB Output is correct
3 Correct 369 ms 27836 KB Output is correct
4 Correct 245 ms 25508 KB Output is correct
5 Correct 331 ms 15052 KB Output is correct
6 Correct 311 ms 15680 KB Output is correct
7 Correct 324 ms 15528 KB Output is correct
8 Correct 317 ms 15568 KB Output is correct
9 Correct 265 ms 15308 KB Output is correct
10 Correct 230 ms 16952 KB Output is correct
11 Correct 221 ms 16944 KB Output is correct
12 Correct 242 ms 15532 KB Output is correct
13 Correct 248 ms 16192 KB Output is correct
14 Correct 307 ms 16092 KB Output is correct
15 Execution timed out 1090 ms 16180 KB Time limit exceeded
16 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 Correct 531 ms 15932 KB Output is correct
3 Correct 517 ms 15992 KB Output is correct
4 Correct 426 ms 16000 KB Output is correct
5 Correct 237 ms 15936 KB Output is correct
6 Correct 594 ms 16148 KB Output is correct
7 Execution timed out 1089 ms 16160 KB Time limit exceeded
8 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 357 ms 17852 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 5 ms 340 KB Output is correct
5 Correct 4 ms 404 KB Output is correct
6 Correct 4 ms 340 KB Output is correct
7 Correct 6 ms 340 KB Output is correct
8 Correct 3 ms 340 KB Output is correct
9 Correct 2 ms 468 KB Output is correct
10 Correct 3 ms 428 KB Output is correct
11 Correct 4 ms 340 KB Output is correct
12 Correct 4 ms 340 KB Output is correct
13 Correct 4 ms 340 KB Output is correct
14 Correct 8 ms 452 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 369 ms 27836 KB Output is correct
18 Correct 245 ms 25508 KB Output is correct
19 Correct 331 ms 15052 KB Output is correct
20 Correct 311 ms 15680 KB Output is correct
21 Correct 324 ms 15528 KB Output is correct
22 Correct 317 ms 15568 KB Output is correct
23 Correct 265 ms 15308 KB Output is correct
24 Correct 230 ms 16952 KB Output is correct
25 Correct 221 ms 16944 KB Output is correct
26 Correct 242 ms 15532 KB Output is correct
27 Correct 248 ms 16192 KB Output is correct
28 Correct 307 ms 16092 KB Output is correct
29 Execution timed out 1090 ms 16180 KB Time limit exceeded
30 Halted 0 ms 0 KB -