Submission #603678

#	Time	Username	Problem	Language	Result	Execution time	Memory
603678		MrDeboo	Stranded Far From Home (BOI22_island)	C++17	10 / 100	1084 ms	22892 KiB

island

#include <bits/stdc++.h>
#define int long long
using namespace std;
signed main(){
    int n,m;
    cin>>n>>m;
    int val[n+1];
    for(int i=1;i<=n;i++)cin>>val[i];
    vector<int>vct[n+1];
    while(m--){
        int x,y;
        cin>>x>>y;
        vct[x].push_back(y);
        vct[y].push_back(x);
    }
    string s(n+1,'1');
    vector<bool>done(n+1);
    srand(43654634);
    vector<pair<int,int>>vv,V;
    for(int i=1;i<=n;i++)V.push_back({val[i],i});
    for(auto &[ii,i]:V){
        if(done[i])continue;
        vector<int>v;
        vector<bool>vis(n+1);
        priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>pq;
        pq.push({0,i});
        int tot=0;
        bool bl=1;
        while(pq.size()){
            int a=pq.top().second,b=pq.top().first;
            pq.pop();
            if(vis[a])continue;
            vis[a]=1;
            if(b>tot)break;
            v.push_back(a);
            tot+=val[a];
            for(auto &w:vct[a]){
                pq.push({val[w],w});
            }
        }
        if(v.size()==n){
            deque<pair<int,int>>dq={{i,val[i]}};
            for(auto &w:v)vis[w]=0;
            while(dq.size()){
                int a=dq.front().first,b=dq.front().second;
                dq.pop_front();
                if(vis[a])continue;
                vis[a]=1;
                if(val[a]>=b){
                    done[a]=1;
                    s[a]='1';
                    b=val[a];
                }
                for(auto &w:vct[a]){
                    dq.push_back({w,b});
                }
            }
        }else{
            for(auto &i:v){
                done[i]=1;
                s[i]='0';
            }
        }
    }
    cout<<s.substr(1,n);
}

Compilation message (stderr)

island.cpp: In function 'int main()':
island.cpp:41:20: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   41 |         if(v.size()==n){
      |            ~~~~~~~~^~~
island.cpp:28:14: warning: unused variable 'bl' [-Wunused-variable]
   28 |         bool bl=1;
      |              ^~

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