제출 #1356541

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1356541		12345678	Stranded Far From Home (BOI22_island)	C++17	100 / 100	262 ms	43756 KiB

island

#include <bits/stdc++.h>

using namespace std;

#define ll long long

const int nx=2e5+5;

ll n, m, s[nx], u, v, on[nx], res[nx];
ll dsu[nx], sm[nx];
vector<ll> adj[nx];
set<ll> nd[nx];
vector<pair<ll, ll>> srt;

int find(int x)
{
    if (dsu[x]==x) return x;
    return dsu[x]=find(dsu[x]);
}

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>m;
    for (int i=1; i<=n; i++) cin>>s[i], srt.push_back({s[i], i}), sm[i]=s[i], dsu[i]=i, nd[i].insert(i);
    for (int i=1; i<=m; i++) cin>>u>>v, adj[u].push_back(v), adj[v].push_back(u);
    sort(srt.begin(), srt.end());
    for (auto [w, u]:srt)
    {
        on[u]=1;
        for (auto v:adj[u])
        {
            if (!on[v]||find(v)==find(u)) continue;
            if (sm[find(v)]<w) nd[find(v)].clear(), sm[u]+=sm[find(v)], dsu[find(v)]=u;
            else
            {
                sm[u]+=sm[find(v)];
                if (nd[find(v)].size()>nd[u].size()) swap(nd[find(v)], nd[u]);
                for (auto x:nd[find(v)]) nd[u].insert(x);
                nd[find(v)].clear();
                dsu[find(v)]=u;
            }
        }
    }
    // for (int i=1; i<=n; i++) cout<<"i "<<i<<' '<<find(i)<<'\n';
    for (auto u:nd[find(1)]) res[u]=1;
    for (int i=1; i<=n; i++) cout<<res[i];
}

• 서브태스크 1: 10 / 10
• 서브태스크 2: 10 / 10
• 서브태스크 3: 15 / 15
• 서브태스크 4: 30 / 30
• 서브태스크 5: 35 / 35