Submission #850342

#	Time	Username	Problem	Language	Result	Execution time	Memory
850342		BidoTeima	Stranded Far From Home (BOI22_island)	C++17	0 / 100	86 ms	16628 KiB

island

#include <bits/stdc++.h>

typedef long long ll;
using namespace std; 
const int N = 2e5 + 3;
vector<int>adj[N];
int s[N];
bool solve_1(int x){
    using _Ty = pair<int,int>;
    priority_queue<_Ty, vector<_Ty>, greater<_Ty>>cur;
    for(int y:adj[x])cur.push({s[y],y});
    ll sz = s[x];
    bool vis[2005]{};
    vis[x]=1;
    while(cur.size()){ 
        int req = cur.top().first;
        int node = cur.top().second;
        cur.pop();
        if(vis[node])
            continue;
        vis[node] = 1;
        if(req>sz)
            return 0;
        sz += req;
        for(int ch : adj[node]){
            cur.push({ch, s[ch]});
        }
    }
    return 1;
}
int main()
{ 
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);    
    int n,m;
    cin>>n>>m;
    for(int i = 1; i <= n; i++)cin>>s[i];
    bool sub3=1;
    for(int i = 0; i < m; i++){
        int a,b;
        cin>>a>>b;
        adj[a].push_back(b);
        adj[b].push_back(a);
        sub3&=abs(a-b)==1;
    }
    if(n <= 2000 && m <= 2000){
        for(int i = 1; i <= n; i++)cout<<solve_1(i);
    }
    return 0;
}

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