oj.uz

Submission #727567

# Submission time Handle Problem Language Result Execution time Memory
727567 2023-04-21T01:14:23 Z horiseun Stranded Far From Home (BOI22_island) C++11
10 / 100
 1000 ms 12948 KB 
#include <iostream>
#include <vector>
#include <tuple>
#include <queue>
#include <stack>
#include <deque>
#include <set>
#include <map>
#include <cmath>
#include <random>
#include <string>
#include <cassert>
#include <climits>
#include <algorithm>
#include <unordered_set>
#include <unordered_map>
using namespace std;

#define ll long long

int n, m, s[200005];
ll sm[200005];
vector<int> adj[200005];
bool seen[200005];

bool bfs(int start) {
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push({s[start], start});
    while (!pq.empty()) {
        ll v; int curr; tie(v, curr) = pq.top();
        pq.pop();
        seen[curr] = true;
        if (v > sm[start] && curr != start) return false;
        sm[start] += v;
        for (int i : adj[curr]) {
            if (!seen[i]) {
                pq.push({s[i], i});
            }
        }
    }
    return true;
}

int main() {

    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> s[i];
    }   
    for (int i = 0, a, b; i < m; i++) {
        cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }

    for (int i = 1; i <= n; i++) {
        fill(seen, seen + 200005, false);
        cout << bfs(i);
    }
    cout << "\n";

}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5204 KB Output is correct
2 Correct 3 ms 5204 KB Output is correct
3 Correct 3 ms 5204 KB Output is correct
4 Correct 225 ms 5304 KB Output is correct
5 Correct 161 ms 5332 KB Output is correct
6 Correct 301 ms 5316 KB Output is correct
7 Correct 229 ms 5336 KB Output is correct
8 Correct 184 ms 5300 KB Output is correct
9 Correct 202 ms 5332 KB Output is correct
10 Correct 71 ms 5460 KB Output is correct
11 Correct 68 ms 5332 KB Output is correct
12 Correct 74 ms 5332 KB Output is correct
13 Correct 119 ms 5308 KB Output is correct
14 Correct 95 ms 5308 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5204 KB Output is correct
2 Correct 3 ms 5204 KB Output is correct
3 Execution timed out 1064 ms 12948 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5204 KB Output is correct
2 Execution timed out 1080 ms 12168 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 5204 KB Output is correct
2 Execution timed out 1077 ms 12312 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5204 KB Output is correct
2 Correct 3 ms 5204 KB Output is correct
3 Correct 3 ms 5204 KB Output is correct
4 Correct 225 ms 5304 KB Output is correct
5 Correct 161 ms 5332 KB Output is correct
6 Correct 301 ms 5316 KB Output is correct
7 Correct 229 ms 5336 KB Output is correct
8 Correct 184 ms 5300 KB Output is correct
9 Correct 202 ms 5332 KB Output is correct
10 Correct 71 ms 5460 KB Output is correct
11 Correct 68 ms 5332 KB Output is correct
12 Correct 74 ms 5332 KB Output is correct
13 Correct 119 ms 5308 KB Output is correct
14 Correct 95 ms 5308 KB Output is correct
15 Correct 3 ms 5204 KB Output is correct
16 Correct 3 ms 5204 KB Output is correct
17 Execution timed out 1064 ms 12948 KB Time limit exceeded
18 Halted 0 ms 0 KB -