제출 #727563

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
727563		horiseun	Stranded Far From Home (BOI22_island)	C++11	0 / 100	1098 ms	13180 KiB

island

#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[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()) {
        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
• Subtask 2: 0 / 10
• Subtask 3: 0 / 15
• Subtask 4: 0 / 30
• Subtask 5: 0 / 35