oj.uz

Submission #722989

# Submission time Handle Problem Language Result Execution time Memory
722989 2023-04-13T06:56:59 Z yahyobekabdunazarov Stranded Far From Home (BOI22_island) C++17
10 / 100
 316 ms 15568 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 5 ms 6740 KB Output is correct
2 Correct 5 ms 6740 KB Output is correct
3 Correct 5 ms 6740 KB Output is correct
4 Correct 198 ms 6836 KB Output is correct
5 Correct 243 ms 6740 KB Output is correct
6 Correct 281 ms 6740 KB Output is correct
7 Correct 210 ms 6740 KB Output is correct
8 Correct 149 ms 6740 KB Output is correct
9 Correct 316 ms 6868 KB Output is correct
10 Correct 106 ms 6740 KB Output is correct
11 Correct 89 ms 6740 KB Output is correct
12 Correct 107 ms 6748 KB Output is correct
13 Correct 129 ms 6740 KB Output is correct
14 Correct 104 ms 6740 KB Output is correct

Subtask #2
0 / 10.0

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

Subtask #3
0 / 15.0

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

Subtask #4
0 / 30.0

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

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 6740 KB Output is correct
2 Correct 5 ms 6740 KB Output is correct
3 Correct 5 ms 6740 KB Output is correct
4 Correct 198 ms 6836 KB Output is correct
5 Correct 243 ms 6740 KB Output is correct
6 Correct 281 ms 6740 KB Output is correct
7 Correct 210 ms 6740 KB Output is correct
8 Correct 149 ms 6740 KB Output is correct
9 Correct 316 ms 6868 KB Output is correct
10 Correct 106 ms 6740 KB Output is correct
11 Correct 89 ms 6740 KB Output is correct
12 Correct 107 ms 6748 KB Output is correct
13 Correct 129 ms 6740 KB Output is correct
14 Correct 104 ms 6740 KB Output is correct
15 Correct 4 ms 6740 KB Output is correct
16 Correct 6 ms 6740 KB Output is correct
17 Incorrect 271 ms 15568 KB Output isn't correct
18 Halted 0 ms 0 KB -