oj.uz

Submission #722975

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

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 184 ms 6740 KB Output is correct
5 Correct 162 ms 6740 KB Output is correct
6 Correct 215 ms 6740 KB Output is correct
7 Correct 180 ms 6740 KB Output is correct
8 Correct 117 ms 6740 KB Output is correct
9 Correct 250 ms 6868 KB Output is correct
10 Correct 81 ms 6740 KB Output is correct
11 Correct 71 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 115 ms 6740 KB Output is correct

Subtask #2
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 Execution timed out 1052 ms 15192 KB Time limit exceeded
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 Execution timed out 1058 ms 12916 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6740 KB Output is correct
2 Execution timed out 1064 ms 14264 KB Time limit exceeded
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 184 ms 6740 KB Output is correct
5 Correct 162 ms 6740 KB Output is correct
6 Correct 215 ms 6740 KB Output is correct
7 Correct 180 ms 6740 KB Output is correct
8 Correct 117 ms 6740 KB Output is correct
9 Correct 250 ms 6868 KB Output is correct
10 Correct 81 ms 6740 KB Output is correct
11 Correct 71 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 115 ms 6740 KB Output is correct
15 Correct 5 ms 6740 KB Output is correct
16 Correct 3 ms 6740 KB Output is correct
17 Execution timed out 1052 ms 15192 KB Time limit exceeded
18 Halted 0 ms 0 KB -