oj.uz

Submission #722984

# Submission time Handle Problem Language Result Execution time Memory
722984 2023-04-13T06:50:41 Z yahyobekabdunazarov Stranded Far From Home (BOI22_island) C++17
10 / 100
 253 ms 15536 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;
		}
	}
}

Compilation message

island.cpp: In function 'int main()':
island.cpp:31:7: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
   31 |  if(n <= 2000 & m <= 2000){
      |     ~~^~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 6740 KB Output is correct
2 Correct 3 ms 6740 KB Output is correct
3 Correct 3 ms 6740 KB Output is correct
4 Correct 163 ms 6740 KB Output is correct
5 Correct 155 ms 6740 KB Output is correct
6 Correct 210 ms 6740 KB Output is correct
7 Correct 175 ms 6740 KB Output is correct
8 Correct 114 ms 6740 KB Output is correct
9 Correct 216 ms 6868 KB Output is correct
10 Correct 79 ms 6836 KB Output is correct
11 Correct 78 ms 6740 KB Output is correct
12 Correct 80 ms 6740 KB Output is correct
13 Correct 120 ms 6740 KB Output is correct
14 Correct 101 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 3 ms 6740 KB Output is correct
3 Incorrect 253 ms 15536 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 245 ms 14412 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 251 ms 15512 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 3 ms 6740 KB Output is correct
3 Correct 3 ms 6740 KB Output is correct
4 Correct 163 ms 6740 KB Output is correct
5 Correct 155 ms 6740 KB Output is correct
6 Correct 210 ms 6740 KB Output is correct
7 Correct 175 ms 6740 KB Output is correct
8 Correct 114 ms 6740 KB Output is correct
9 Correct 216 ms 6868 KB Output is correct
10 Correct 79 ms 6836 KB Output is correct
11 Correct 78 ms 6740 KB Output is correct
12 Correct 80 ms 6740 KB Output is correct
13 Correct 120 ms 6740 KB Output is correct
14 Correct 101 ms 6740 KB Output is correct
15 Correct 4 ms 6740 KB Output is correct
16 Correct 3 ms 6740 KB Output is correct
17 Incorrect 253 ms 15536 KB Output isn't correct
18 Halted 0 ms 0 KB -