Submission #580176

#	Time	Username	Problem	Language	Result	Execution time	Memory
580176		wdjpng	Stranded Far From Home (BOI22_island)	C++17	10 / 100	1097 ms	38360 KiB

island

#include <bits/stdc++.h>

#define int long long
#define double long double
#define rep(i,n) for(int i =0; i<n; i++)
#define all(a) a.begin(),a.end()

using namespace std;

int n,m;
vector<int>s;
vector<vector<int>>E;
vector<int>chef(2e5+1);

struct uni
{
    int sum=0;
    set<int>bord;
};

vector<uni>unis(2e5+1);

int find(int a)
{
    if(a==chef[a]) return a;
    return chef[a]=find(chef[a]);
}

void unite(int a, int b) {
    a=find(a);
    b=find(b);
    if(unis[b].bord.size()>unis[a].bord.size()) swap(a,b);
    for(int i : unis[b].bord) if(!unis[a].bord.count(i)) {unis[a].sum+=s[i]; unis[a].bord.insert(i);}
}

bool sorti(int a, int b)
{
    return s[a]<s[b];
}
signed main()
{
    cin>>n>>m;
    if(n==1) {cout<<"1\n"; exit(0);}
    s.resize(n);
    rep(i,n) cin>>s[i];

    E.resize(n);
    rep(i,m)
    {
        int a,b;
        cin>>a>>b;
        a--;
        b--;
        E[a].push_back(b);
        E[b].push_back(a);
    }

    rep(i,n)
    {
        chef[i]=i;
        unis[i].bord.insert(i);
        unis[i].sum=s[i];
    }

    vector<int>ord(n);
    rep(i,n) ord[i]=i;

    int totsum=0;
    rep(i,n) totsum+=s[i];

    sort(all(ord), sorti);
    vector<bool>sol(n,false);
    rep(v,n)
    {
        int sum = s[v];
        vector<bool>vis(n,false);
        vis[v]=true;

        bool ischange=true, halt=false;
        priority_queue<pair<int,int>,vector<pair<int,int>>, greater<pair<int,int>>>pq;
        for(int w : E[v]) if(!vis[w]) {pq.push({s[w],w}); vis[w]=true;}
        while (pq.size()&&pq.top().first<=sum&&!halt)
        {
            auto blub=pq.top();
            pq.pop();

            sum+=blub.first;
            for(int w : E[blub.second]) if(!vis[w]) {pq.push({s[w],w}); vis[w]=true;}
            halt|=sum==totsum||sol[blub.second];
        }
        sol[v]=halt;
    }

    rep(i,n) cout<<(sol[i]?'1':'0');
    cout<<'\n';
}   

Compilation message (stderr)

island.cpp: In function 'int main()':
island.cpp:79:14: warning: unused variable 'ischange' [-Wunused-variable]
   79 |         bool ischange=true, halt=false;
      |              ^~~~~~~~

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