oj.uz

Submission #722996

# Submission time Handle Problem Language Result Execution time Memory
722996 2023-04-13T07:02:13 Z yahyobekabdunazarov Stranded Far From Home (BOI22_island) C++17
10 / 100
 250 ms 15516 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 <= 10000 && m <= 10000){
		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 5 ms 6740 KB Output is correct
3 Correct 3 ms 6740 KB Output is correct
4 Correct 174 ms 6740 KB Output is correct
5 Correct 167 ms 6836 KB Output is correct
6 Correct 210 ms 6740 KB Output is correct
7 Correct 204 ms 6740 KB Output is correct
8 Correct 113 ms 6740 KB Output is correct
9 Correct 246 ms 6868 KB Output is correct
10 Correct 77 ms 6740 KB Output is correct
11 Correct 73 ms 6740 KB Output is correct
12 Correct 72 ms 6740 KB Output is correct
13 Correct 121 ms 6740 KB Output is correct
14 Correct 134 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 4 ms 6740 KB Output is correct
3 Incorrect 237 ms 15508 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 250 ms 14492 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 244 ms 15516 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 5 ms 6740 KB Output is correct
3 Correct 3 ms 6740 KB Output is correct
4 Correct 174 ms 6740 KB Output is correct
5 Correct 167 ms 6836 KB Output is correct
6 Correct 210 ms 6740 KB Output is correct
7 Correct 204 ms 6740 KB Output is correct
8 Correct 113 ms 6740 KB Output is correct
9 Correct 246 ms 6868 KB Output is correct
10 Correct 77 ms 6740 KB Output is correct
11 Correct 73 ms 6740 KB Output is correct
12 Correct 72 ms 6740 KB Output is correct
13 Correct 121 ms 6740 KB Output is correct
14 Correct 134 ms 6740 KB Output is correct
15 Correct 4 ms 6740 KB Output is correct
16 Correct 4 ms 6740 KB Output is correct
17 Incorrect 237 ms 15508 KB Output isn't correct
18 Halted 0 ms 0 KB -