Submission #1305727

#	Time	Username	Problem	Language	Result	Execution time	Memory
1305727		thesentro	Stranded Far From Home (BOI22_island)	C++20	100 / 100	257 ms	58196 KiB

island

/*
 _____ _          ____             _             
|_   _| |__   ___/ ___|  ___ _ __ | |_ _ __ ___  
  | | | '_ \ / _ \___ \ / _ \ '_ \| __| '__/ _ \ 
  | | | | | |  __/___) |  __/ | | | |_| | | (_) |
  |_| |_| |_|\___|____/ \___|_| |_|\__|_|  \___/ 
*/
 
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
using namespace std;
#define ll long long
ll mod = 1e9+7;
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
ll binpow(ll a, ll b)
{
    ll res = 1;
    while (b>0)
    {
        if (b&1)
            res = (res*a)%mod;
        a = (a*a)%mod;
        b>>=1;
    }
    return res;
}
ll gcd(ll x, ll y)
{
    if (y==0)
        return x;
    return gcd(y, x%y);
}
ll maxi =505050;
vector<vector<ll>>g(maxi);
vector<ll>vis(maxi, 0), v(maxi);
struct DSU
{
    vector<ll>e;
    vector<vector<ll>>ans;
    vector<ll>val;
    void init(ll n)
    {
        e.resize(n+1, -1);
        val.resize(n+1);
        ans.resize(n+1);
        for (int i=1 ; i<=n ;i++){
            val[i] = v[i];
            ans[i].push_back(i);}
    }
    ll find (ll x)
    {
        if (e[x]<0)
            return x;
        return e[x] = find(e[x]);
    }
    bool merge(ll x, ll y)
    {
        y = find(y);
        if (v[x]>val[y])
            ans[y].clear();
        x = find(x);
        if (x==y)
            return false;
        if (ans[x].size()<ans[y].size()) swap(x,y);
        for (auto i:ans[y]) ans[x].push_back(i);
        ans[y].clear();
        val[x] += val[y];
        e[x] += e[y];
        e[y] = x;
        return true;
    }
};
void solve()
{   
    ll n,m;
    cin>>n>>m;
    for (int i=1 ; i<=n ;i++)
        cin>>v[i];
    vector<pair<ll,ll>>vp;
    vector<vector<ll>>adj(n+1);
    for (int i=1 ; i<=m ; i++)
    {
        ll x,y;
        cin>>x>>y;
        if (v[x]>v[y])
            adj[x].push_back(y);
        else
            adj[y].push_back(x);
    }
    for (int i=1 ; i<=n ; i++) vp.push_back({v[i], i});
    sort(vp.begin(), vp.end());
    DSU dsu;
    dsu.init(n);
    for (auto it:vp)
    {
        ll x = it.second;
        for (auto i:adj[x])
            dsu.merge(x, i);
        // cout<<"Hmm"<<" "<<x<<endl;
    }
    // cout<<"Salam"<<endl;
    string s(n, '0');
    for (int i=1 ; i<=n ; i++)
    {
        for (auto j:dsu.ans[i])
            s[j-1] = '1';
        // cout<<i<<"    ";
        // for (auto j:dsu.ans[i]) cout<<j<<" ";
        // cout<<endl;
    }   
    cout<<s<<endl;
}
int main()
{
    ll tt = 1;
    // cin>>tt;
    while (tt--)
    {
        solve();
    }
    return 0;
}

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