Submission #1090424

#	Time	Username	Problem	Language	Result	Execution time	Memory
1090424		jamkel	Stranded Far From Home (BOI22_island)	C++14	100 / 100	156 ms	34132 KiB

island

#include<bits/stdc++.h>
using namespace std;
#define all(x) x.begin(),x.end()
#define st first
#define nd second
typedef long long ll;
ll f(vector<ll>&u,ll i)
{
    if(u[i]==i)
    {
        return i;
    }
    u[i]=f(u,u[i]);
    return u[i];
}
void f2(vector<ll>&u,vector<ll>&w,ll i)
{
    if(u[i]==i)
    {
        w[i]=2;
        return;
    }
    if(w[i]>0)
    {
        return;
    }
    f2(u,w,u[i]);
    w[i]=w[u[i]];
}
int main()
{
    ios_base::sync_with_stdio(false);cin.tie(0);
    ll n,m;
    cin>>n>>m;
    vector<ll>a(n);
    vector<pair<ll,ll>>c(n);
    vector<vector<ll>>b(n);
    vector<ll>d(n);
    for(ll i=0;i<n;i++)
    {
        cin>>c[i].st;
        c[i].nd=i;
        a[i]=c[i].st;
        d[i]=a[i];
    }
    sort(all(c));
    for(ll i=0;i<m;i++)
    {
        ll x,y;
        cin>>x>>y;
        b[x-1].push_back(y-1);
        b[y-1].push_back(x-1);
    }
    vector<ll>u1(n);
    vector<ll>u2(n);
    vector<bool>wyn(n,false);
    for(ll i=0;i<n;i++)
    {
        u1[i]=i;
        u2[i]=i;
    }
    for(ll q=0;q<n;q++)
    {
        ll i=c[q].nd;
        ll wag=0;
        for(ll j=0;j<b[i].size();j++)
        {
            if(f(u1,b[i][j])!=i)
            {
                if(a[b[i][j]]<a[i] or (a[b[i][j]]==a[i] && i>b[i][j]))
                {
                    if(d[f(u1,b[i][j])]<a[i])
                    {
                        wyn[f(u1,b[i][j])]=true;
                    }
                    wag+=d[u1[b[i][j]]];
                    u2[u1[b[i][j]]]=i;
                    u1[u1[b[i][j]]]=i;
                    
                }
            }
        }
        d[i]+=wag;
    }
    vector<ll>ww(n);
    for(ll i=0;i<n;i++)
    {
        ww[i]=wyn[i];
    }
    for(ll i=0;i<n;i++)
    {
        if(ww[i]==0)
        {
            f2(u2,ww,i);
        }
        cout<<ww[i]-1;
    }
    cout<<endl;
}

Compilation message (stderr)

island.cpp: In function 'int main()':
island.cpp:66:21: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |         for(ll j=0;j<b[i].size();j++)
      |                    ~^~~~~~~~~~~~

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