제출 #1256420

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1256420		BigBadBully	Stranded Far From Home (BOI22_island)	C++20	35 / 100	1095 ms	76716 KiB

island

#include <bits/stdc++.h>
#define int long long
#define pii pair<int, int>
#define ff first
#define ss second
using namespace std;
const int inf = 1e18 + 5;
const int mod = 1e9 + 7;
const int maxm = 5e6 + 1;
const pii bad = {inf, inf};
using ll = long long;
using ld = long double;

void solve()
{
    int n, m;
    cin >> n >> m;
    vector<int> v(n);
    for (int i = 0; i < n; i++)
        cin >> v[i];

    vector<priority_queue<pii, vector<pii>, greater<pii>>> graph(n);
    for (int i = 0; i < m; i++)
    {
        int a, b;
        cin >> a >> b;
        graph[--a].push({v[--b], b});
        graph[b].push({v[a], a});
    }
    auto adj = graph;
    vector<pii> orig(n);
    for (int i = 0; i < n; i++)
        orig[i] = {v[i], i};
    sort(orig.begin(), orig.end());
    vector<int> par(n, 0);
    for (int i = 0; i < n; i++)
        par[i] = i;
    auto sz = v;
    function<int(int)> fnd = [&](int x) -> int
    {
        if (par[x] == x)
            return x;
        return par[x] = fnd(par[x]);
    };
    auto unite = [&](int a, int b)
    {
        a = fnd(a), b = fnd(b);
        if(a==b)return;
        if (graph[a].size() > graph[b].size())
            swap(a, b);
        while (graph[a].size())
            graph[b].push(graph[a].top()), graph[a].pop();
        par[a] = b;
        sz[b] += sz[a];
    };
    vector<int> af(n, -1);
    orig.push_back({inf, inf});
    int l = 0;
    for (int r = 1; r <= n; r++)
    {
        if (orig[r].ff != orig[r - 1].ff)
        {
            for (int i = l; i < r; i++)
            {
                int idx = orig[i].ss;
                while(adj[idx].size() && adj[idx].top().ff <= orig[i].ff)
                    unite(adj[idx].top().ss,idx),adj[idx].pop();
            }   
            for (int i = l; i < r; i++)
            {
                int idx = fnd(orig[i].ss);
                int ri = orig[i].ss;
                while(graph[idx].size() && graph[idx].top().ff <= orig[i].ff)
                    graph[idx].pop();
                auto gurt = graph[idx];
                if (gurt.empty())
                    af[ri] = ri;
                else if (sz[fnd(ri)] >= gurt.top().ff)
                    af[ri] = gurt.top().ss;
            }
            l = r;
        }
    }
    fnd = [&](int x)->int
    {
        if (af[x] == -1)return -1;
        if (af[x]==x)return x;
        return af[x] = fnd(af[x]);
    };
    for (int i = 0; i < n; i++)
    {
        if (fnd(i)>=0)
            cout << '1';
        else
            cout << '0';
    }
    cout << '\n';
}


signed main()
{

    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    solve();
}

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