Submission #1110479

#	Time	Username	Problem	Language	Result	Execution time	Memory
1110479		_callmelucian	Stranded Far From Home (BOI22_island)	C++14	100 / 100	769 ms	61464 KiB

island

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pl;
typedef pair<int,int> pii;
typedef tuple<int,int,int> tt;

#define all(a) a.begin(), a.end()
#define filter(a) a.erase(unique(all(a)), a.end())

const int mn = 2e5 + 5;
int cost[mn], recur[mn], dp[mn];
vector<int> adj[mn], pos[mn];

struct customComp {
    bool operator() (int a, int b) const {
        return cost[a] < cost[b];
    }
};

struct DSU {
    vector<ll> lab, weight;
    vector<set<int, customComp>> adjSet;

    DSU (int sz) : lab(sz + 1), weight(sz + 1, 0), adjSet(sz + 1) {
        for (int i = 1; i <= sz; i++)
            adjSet[i] = set<int, customComp>(all(adj[i])), weight[i] = cost[i];
        return;
    }

    int get (int u) {
        if (!lab[u]) return u;
        return lab[u] = get(lab[u]);
    }

    void unite (int a, int b) {
        a = get(a), b = get(b);
        if (a == b) return;
        if (adjSet[a].size() < adjSet[b].size()) swap(a, b);
        for (int u : adjSet[b]) adjSet[a].insert(u);
        lab[b] = a, weight[a] += weight[b];
        adjSet[b].clear();
    }

    int getRecur (int u) {
        int root = get(u);
        auto it = adjSet[root].upper_bound(u);
        if (it == adjSet[root].end()) return INT_MAX;
        return (weight[root] >= weight[*it] ? *it : 0);
    }
};

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n, m; cin >> n >> m;
    vector<int> cmp;
    for (int i = 1; i <= n; i++) {
        cin >> cost[i];
        cmp.push_back(cost[i]);
    }
    sort(all(cmp)), filter(cmp);

    for (int i = 1; i <= n; i++) {
        int idx = lower_bound(all(cmp), cost[i]) - cmp.begin();
        pos[idx].push_back(i);
    }

    while (m--) {
        int a, b; cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }

    DSU dsu(n);
    for (int iter = 0; iter < cmp.size(); iter++) {
        for (int i : pos[iter]) {
            for (int j : adj[i])
                if (cost[j] <= cost[i]) dsu.unite(i, j);
        }
        for (int i : pos[iter]) recur[i] = dsu.getRecur(i);
    }

    for (int iter = cmp.size() - 1; iter >= 0; iter--) {
        for (int i : pos[iter]) {
            if (recur[i] == INT_MAX) dp[i] = 1;
            else if (recur[i]) dp[i] = dp[recur[i]];
        }
    }
    for (int i = 1; i <= n; i++) cout << dp[i];

    return 0;
}

Compilation message (stderr)

island.cpp: In function 'int main()':
island.cpp:80:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |     for (int iter = 0; iter < cmp.size(); iter++) {
      |                        ~~~~~^~~~~~~~~~~~

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