oj.uz

Submission #722987

# Submission time Handle Problem Language Result Execution time Memory
722987 2023-04-13T06:54:47 Z yahyobekabdunazarov Stranded Far From Home (BOI22_island) C++17
10 / 100
 276 ms 15708 KB 
#include <bits/stdc++.h>
#define ff first
#define ss second
#define int long long
using namespace std;
const int MAX_N = 2e5 + 9;
vector<int> adj[MAX_N], weights(MAX_N, 0);

bool visited[MAX_N];
priority_queue <pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
void add_children(int u){
	for(int i: adj[u]){
		if(visited[i]) continue;
		visited[i] = 1;
		pq.push(make_pair(weights[i], i)); 
	}
}
signed main() {
    int n, m, right = 0;
    cin >> n >> m;
    for(int i = 1; i <= n; i++){
		cin >> weights[i];
		right += weights[i];
	}
    for(int i = 0; i < m; i++){
		int x, y;
		cin >> x >> y;
		adj[y].push_back(x);
		adj[x].push_back(y);
	}
	if(n <= 2000 && m <= 2000){
		for(int i = 1; i <= n; i++){
			int sum = weights[i];
			visited[i] = 1;
			add_children(i);
			while(!pq.empty() && pq.top().ff <= sum){
				sum += pq.top().ff;
				int u = pq.top().ss;
				pq.pop();
				add_children(u);
			}
			cout << (sum >= right);
			pq = priority_queue <pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>>();
			fill(visited, visited + MAX_N, false);
			
		}
	}
	else{
		int dp[n + 1];
		dp[0] = 0;
		for(int i = 1; i <= n; i++){
			dp[i] = dp[i - 1] + weights[i];
		}
		int prev = 1;
		for(int i = 1; i <= n; i++){
			prev = (prev && (dp[n] - dp[i - 1]) >= weights[i - 1])	;
			cout << prev;
		}
	}
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6740 KB Output is correct
2 Correct 4 ms 6740 KB Output is correct
3 Correct 3 ms 6740 KB Output is correct
4 Correct 162 ms 6756 KB Output is correct
5 Correct 164 ms 6740 KB Output is correct
6 Correct 228 ms 6740 KB Output is correct
7 Correct 166 ms 6740 KB Output is correct
8 Correct 119 ms 6740 KB Output is correct
9 Correct 248 ms 6868 KB Output is correct
10 Correct 91 ms 6788 KB Output is correct
11 Correct 74 ms 6740 KB Output is correct
12 Correct 76 ms 6740 KB Output is correct
13 Correct 121 ms 6740 KB Output is correct
14 Correct 124 ms 6740 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6740 KB Output is correct
2 Correct 3 ms 6740 KB Output is correct
3 Incorrect 252 ms 15624 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6740 KB Output is correct
2 Incorrect 276 ms 14468 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6740 KB Output is correct
2 Incorrect 249 ms 15708 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6740 KB Output is correct
2 Correct 4 ms 6740 KB Output is correct
3 Correct 3 ms 6740 KB Output is correct
4 Correct 162 ms 6756 KB Output is correct
5 Correct 164 ms 6740 KB Output is correct
6 Correct 228 ms 6740 KB Output is correct
7 Correct 166 ms 6740 KB Output is correct
8 Correct 119 ms 6740 KB Output is correct
9 Correct 248 ms 6868 KB Output is correct
10 Correct 91 ms 6788 KB Output is correct
11 Correct 74 ms 6740 KB Output is correct
12 Correct 76 ms 6740 KB Output is correct
13 Correct 121 ms 6740 KB Output is correct
14 Correct 124 ms 6740 KB Output is correct
15 Correct 3 ms 6740 KB Output is correct
16 Correct 3 ms 6740 KB Output is correct
17 Incorrect 252 ms 15624 KB Output isn't correct
18 Halted 0 ms 0 KB -