Submission #837213

#	Time	Username	Problem	Language	Result	Execution time	Memory
837213		Hanksburger	Stranded Far From Home (BOI22_island)	C++17	100 / 100	199 ms	46636 KiB

island

#include <bits/stdc++.h>
using namespace std;
long long s[200005], par[200005], sz[200005], ok[200005];
vector<long long> adj[200005], child[200005];
pair<long long, long long> a[200005];
long long findPar(long long u)
{
    return (par[u]==u)?u:(par[u]=findPar(par[u]));
}
void dfs(long long u)
{
    sz[u]=s[u];
    for (long long v:child[u])
    {
        dfs(v);
        sz[u]+=sz[v];
    }
}
void dfs2(long long u, long long p)
{
    if (sz[u]<s[p])
        return;
    ok[u]=1;
    for (long long v:child[u])
        dfs2(v, u);
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    long long n, m;
    cin >> n >> m;
    for (long long i=1; i<=n; i++)
    {
        cin >> s[i];
        a[i]={s[i], i};
    }
    sort(a+1, a+n+1);
    for (long long i=1; i<=m; i++)
    {
        long long u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    for (long long i=1; i<=n; i++)
        par[i]=i;
    for (long long i=1; i<=n; i++)
    {
        set<long long> ss;
        long long u=a[i].second;
        for (long long v:adj[u])
            if ((s[v]<s[u] || (s[v]==s[u] && v<u)) && ss.find(findPar(v))==ss.end())
                ss.insert(par[v]);
        for (long long v:ss)
        {
            par[v]=u;
            child[u].push_back(v);
        }
    }
    dfs(a[n].second);
    dfs2(a[n].second, 0);
    for (long long i=1; i<=n; i++)
        cout << ok[i];
}

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