Submission #580171

#	Time	Username	Problem	Language	Result	Execution time	Memory
580171		wdjpng	Stranded Far From Home (BOI22_island)	C++17	0 / 100	1097 ms	44924 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);
    for(int v : ord)
    {
        set<int>nodes;
        int sum = 0;
        sum+=s[v];

        nodes.insert(v);

        bool ischange=true, halt=false;
        while (ischange&&!halt)
        {
            ischange=false;
            for(int i : nodes)
            {
                for(int w : E[i])
                {
                    if(s[w]<=sum&&(nodes.count(w)==0))
                    {
                        nodes.insert(w);
                        sum+=s[w];
                        ischange=true;
                        halt|=sum==totsum||sol[w];
                    }
                    if(halt) break;
                }
                if(halt) break;
            }
        }
        sol[v]=halt;
    }

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

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