Submission #949777

#	Time	Username	Problem	Language	Result	Execution time	Memory
949777		Dec0Dedd	Stranded Far From Home (BOI22_island)	C++14	100 / 100	269 ms	30556 KiB

island

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<ll, int> pii;

const int N = 2e5+10;

vector<int> G[N];
vector<pii> v;

ll n, m, s[N], rep[N];

struct dsu {
    vector<ll> p, sz;

    void init(int k) {
        p.resize(k+10);
        sz.assign(k+10, 0);

        for (int i=0; i<k+10; ++i) p[i]=i, sz[i]=s[i];
    }

    int f(int x) {
        if (p[x] == x) return x;
        return p[x]=f(p[x]);
    }

    void mrg(int x, int y) {
        x=f(x), y=f(y);
        if (x == y) return;
        if (s[y] > s[x]) swap(x, y);
        assert(s[x] >= s[y]);
        sz[x]+=sz[y];
        p[y]=x;
        rep[y]=x;
    }
};

ll idx[N], sm[N];

void solve() {
    cin>>n>>m;

    for (int i=1; i<=n; ++i) {
        cin>>s[i];
        v.push_back({s[i], i});
    } sort(v.begin(), v.end());

    for (int i=0; i<n; ++i) idx[v[i].second]=i;

    for (int i=1; i<=m; ++i) {
        int a, b; cin>>a>>b;
        G[a].push_back(b);
        G[b].push_back(a);
    } dsu d; d.init(n+10);

    for (int i=0; i<n; ++i) {
        for (auto u : G[v[i].second]) {
            if (idx[u] < i) d.mrg(v[i].second, u);
        } sm[v[i].second]=d.sz[d.f(v[i].second)];
    }

    bool ans[n+1]={}; ans[v.back().second]=true;
    for (int i=n-2; i>=0; --i) {
        if (ans[rep[v[i].second]] && s[rep[v[i].second]] <= sm[v[i].second]) ans[v[i].second]=true;
    }

    for (int i=1; i<=n; ++i) cout<<ans[i];
    cout<<"\n";
}

int main() {
    int t=1; //cin>>t;
    while (t--) solve();
}

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