Submission #959639

#	Time	Username	Problem	Language	Result	Execution time	Memory
959639		Bidoneczek11	Stranded Far From Home (BOI22_island)	C++14	10 / 100	1082 ms	26392 KiB

island

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define ll long long
#define ld long double
#define pb push_back
#define nd second
#define st first
#define sz size
#define forr(i, n) for(int i=1;i<=n;i++)
const ll infl=1e18+90;
const int inf=1e9+90;
const int roz=2e5+93;

vector<pair<int,int> > wek;
vector<int> graf[roz];
int sum=0, odp[roz], odw[roz], n, val[roz];

void bfs(pair<int, int>  a)
{
    //cerr<<"wszedken\n";
    //cerr<<"a.st "<<a.st<<" a.nd "<<a.nd<<"\n";
    for(int i=1;i<=n;i++) odw[i]=0;
    int x=a.st, y=a.nd;
    priority_queue<pair<int,int> > kol;
    while(!kol.empty()) kol.pop();
    odw[y]=1;
    for(auto it:graf[y])
    {
        kol.push({-val[it], it});
    }
    while(!kol.empty())
    {
        //cerr<<"xdd\n";
        pair<int,int> b=kol.top();
        b.st=-b.st;
        kol.pop();
        //cerr<<"wlazlem dla b= "<<b.st<<" "<<b.nd<<" x = "<<x<<" "<<odw[b.nd]<<"\n";
        if(odw[b.nd]==1) continue;
        odw[b.nd]=1;
        if(b.st>x) break;
        x+=b.st;
        //cerr<<"dodalem\n";
        for(auto it:graf[b.nd])
        {
            if(odw[it]==0)
            {
                kol.push({-val[it], it});
            }
        }
    }
    //cerr<<"wyszedlem\n";
    if(x==sum) odp[y]=1;
    return;
}


signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>val[i];
        wek.pb({val[i], i});
        sum+=val[i];
    }
    sort(wek.begin(), wek.end());
    for(int i=1;i<=m;i++)
    {
        int a, b;
        cin>>a>>b;
        graf[a].pb(b);
        graf[b].pb(a);
    }
    for(int i=n-1;i>=0;i--)
    {
        bfs(wek[i]);
    }
    for(int i=1;i<=n;i++)
    {
        cout<<odp[i];
    }
    cout<<"\n";
}

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