oj.uz

Submission #727560

# Submission time Handle Problem Language Result Execution time Memory
727560 2023-04-21T01:10:10 Z horiseun Stranded Far From Home (BOI22_island) C++11
0 / 100
 1000 ms 59916 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], sm[200005];
vector<int> adj[2000005];
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()) {
        int v, 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 + n + 1, false);
        cout << bfs(i);
    }
    cout << "\n";

}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 47192 KB Output is correct
2 Correct 21 ms 47188 KB Output is correct
3 Correct 22 ms 47284 KB Output is correct
4 Incorrect 24 ms 47316 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 47188 KB Output is correct
2 Correct 24 ms 47296 KB Output is correct
3 Execution timed out 1054 ms 59916 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 47188 KB Output is correct
2 Execution timed out 1043 ms 59820 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 47284 KB Output is correct
2 Execution timed out 1071 ms 59852 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 47192 KB Output is correct
2 Correct 21 ms 47188 KB Output is correct
3 Correct 22 ms 47284 KB Output is correct
4 Incorrect 24 ms 47316 KB Output isn't correct
5 Halted 0 ms 0 KB -