oj.uz

Submission #604072

# Submission time Handle Problem Language Result Execution time Memory
604072 2022-07-24T16:57:51 Z l_reho Stranded Far From Home (BOI22_island) C++14
10 / 100
 1000 ms 27032 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<bool> &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<bool> ans(N, 0);
	
	
	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++){
			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;
				
				if(ans[node]){
					total = sum;
					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;
	}

	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 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 6 ms 340 KB Output is correct
5 Correct 4 ms 340 KB Output is correct
6 Correct 3 ms 396 KB Output is correct
7 Correct 4 ms 340 KB Output is correct
8 Correct 3 ms 340 KB Output is correct
9 Correct 239 ms 444 KB Output is correct
10 Correct 3 ms 340 KB Output is correct
11 Correct 3 ms 340 KB Output is correct
12 Correct 3 ms 340 KB Output is correct
13 Correct 164 ms 416 KB Output is correct
14 Correct 86 ms 340 KB Output is correct

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 282 ms 27032 KB Output is correct
4 Correct 259 ms 24544 KB Output is correct
5 Correct 297 ms 14284 KB Output is correct
6 Correct 310 ms 14776 KB Output is correct
7 Correct 308 ms 14796 KB Output is correct
8 Correct 311 ms 14784 KB Output is correct
9 Correct 280 ms 14552 KB Output is correct
10 Correct 239 ms 16116 KB Output is correct
11 Correct 243 ms 16168 KB Output is correct
12 Correct 245 ms 14924 KB Output is correct
13 Execution timed out 1092 ms 14392 KB Time limit exceeded
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 Correct 518 ms 14500 KB Output is correct
3 Correct 530 ms 14588 KB Output is correct
4 Correct 429 ms 14552 KB Output is correct
5 Execution timed out 1089 ms 14328 KB Time limit exceeded
6 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 322 ms 16860 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 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 6 ms 340 KB Output is correct
5 Correct 4 ms 340 KB Output is correct
6 Correct 3 ms 396 KB Output is correct
7 Correct 4 ms 340 KB Output is correct
8 Correct 3 ms 340 KB Output is correct
9 Correct 239 ms 444 KB Output is correct
10 Correct 3 ms 340 KB Output is correct
11 Correct 3 ms 340 KB Output is correct
12 Correct 3 ms 340 KB Output is correct
13 Correct 164 ms 416 KB Output is correct
14 Correct 86 ms 340 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 282 ms 27032 KB Output is correct
18 Correct 259 ms 24544 KB Output is correct
19 Correct 297 ms 14284 KB Output is correct
20 Correct 310 ms 14776 KB Output is correct
21 Correct 308 ms 14796 KB Output is correct
22 Correct 311 ms 14784 KB Output is correct
23 Correct 280 ms 14552 KB Output is correct
24 Correct 239 ms 16116 KB Output is correct
25 Correct 243 ms 16168 KB Output is correct
26 Correct 245 ms 14924 KB Output is correct
27 Execution timed out 1092 ms 14392 KB Time limit exceeded
28 Halted 0 ms 0 KB -