Submission #1161516

#	Time	Username	Problem	Language	Result	Execution time	Memory
1161516		qrn	Stranded Far From Home (BOI22_island)	C++20	100 / 100	573 ms	86824 KiB

island

#include <bits/stdc++.h>
using namespace std;
 
#define SPEED                     \
    ios_base::sync_with_stdio(0); \
    cin.tie(NULL);                \
    cout.tie(NULL);
 
#define endl "\n"
#define pb push_back
#define intt long long
#define fi first
#define se second
#define ALL(x) x.begin(), x.end()
 
const intt mod = 998244353;
const intt mxN = 5e5 + 5;
const intt L = 19;

vector<vector<intt>> graph;
set<intt> components[mxN];
map<intt, intt> nodes[mxN];
vector<intt> val(mxN);

struct DSU {
    vector<intt> parent, sze, maks;
    DSU(intt n) {
        parent.resize(n + 1);
        sze.resize(n + 1);
        maks.resize(n + 1);
        for(intt i = 1; i <= n;  i++) {
            parent[i] = i;
            sze[i] = val[i];
            components[i].insert(i);
            maks[i] = val[i];
        }
    }

    intt root(intt x) {
        if(parent[x] == x) return x;
        else return parent[x] = root(parent[x]);
    }

    void unite(intt a, intt b) {
        a = root(a);
        b = root(b);
        if(a == b) return;

        if(components[a].size() < components[b].size()) swap(a, b);
        parent[b] = a;
        sze[a] += sze[b];
        maks[a] = max(maks[a], maks[b]);
        for(auto u : components[b]) components[a].insert(u);
        components[b].clear();
    }
};

void solve() {
   intt n, m, lol = 0;
   cin >> n >> m;
   graph.assign(n + 1, vector<intt> {});
   for(intt i = 1; i <= n; i++) {
        cin >> val[i];
        lol = max(lol, val[i]);
   }
   vector<pair<intt,intt>> sorted;
   for(intt i = 1; i <= n; i++) {
        sorted.pb({val[i], i});
   }
   sort(ALL(sorted));
   for(intt i = 0; i < m; i++) {
        intt a, b;
        cin >> a >> b;
        graph[a].pb(b);
        graph[b].pb(a);
   }

//    cout << "13555555555" << endl;

   DSU dsu(n + 55);
   vector<intt> ans(n+1, 1);
   bool first = true;

   for(intt o = 0; o < n; o++) {
        intt curw = sorted[o].fi;
        intt node = sorted[o].se;
        for(auto u : graph[node]) {
            if(dsu.root(u) == dsu.root(node) || dsu.maks[dsu.root(u)] > val[node]) continue;

            if(dsu.sze[dsu.root(u)] < val[node]) {
                for(auto j : components[dsu.root(u)]) {
                    ans[j] = 0;
                }
            }
            dsu.unite(u, node);
        }
   }
   for(intt i = 1; i <= n; i++) {
        cout << ans[i];
   }
   cout << endl;
}

int main() {
    SPEED;
    intt tst = 1;
    // cin >> tst;
    while (tst--) {
        solve();
    }

    return 0;
}

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