Submission #794377

#	Time	Username	Problem	Language	Result	Execution time	Memory
794377		TahirAliyev	Stranded Far From Home (BOI22_island)	C++17	10 / 100	1086 ms	13608 KiB

island

#include <bits/stdc++.h>
 
#pragma GCC optimize("O3")
 
using namespace std;
 
#define ll long long int
#define oo 4e18
#define pii pair<int, int>

const int MAX = 2e5 + 5;

int arr[MAX];
int ans[MAX];
vector<int> g[MAX];
bool collected[MAX];

bool djikstra(int node){
    memset(collected, 0, sizeof(collected));
    ll sum = arr[node];
    collected[node] = 1;
    set<pii> s;
    for(int to : g[node]){
        s.insert({arr[to], to});
    }
    while(!s.empty()){
        pii a = *(s.begin());
        if(a.first > sum){
            return 0;
        }
        sum += a.first;
        collected[a.second] = 1;
        s.erase(s.begin());
        for(int to : g[a.second]){
            if(collected[to]) continue;
            s.insert({arr[to], to});
        }
    }
    return 1;
}

int main(){
    int n, m; cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        cin >> arr[i];
    }
    for (int i = 0; i < m; i++)
    {
        int a, b; cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    for (int i = 1; i <= n; i++)
    {
        cout << djikstra(i);
    }
    
}

• Subtask 1: 10 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 15
• Subtask 4: 0 / 30
• Subtask 5: 0 / 35