Submission #1025303

#	Time	Username	Problem	Language	Result	Execution time	Memory
1025303		overwatch9	Stranded Far From Home (BOI22_island)	C++17	100 / 100	131 ms	40904 KiB

island

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int maxn = 2e5 + 1;
ll S[maxn];
vector <int> adj[maxn];
vector <int> mark[maxn];
bool ans[maxn];
bool inserted[maxn], vis[maxn], in_marked[maxn];
int id[maxn];
struct DSU {
    vector <int> link, sz, lst_added;
    vector <ll> sum;
    DSU (int s) {
        lst_added = link = sz = vector <int> (s+1);
        sum = vector <ll> (s+1);
        for (int i = 1; i <= s; i++) {
            lst_added[i] = link[i] = i;
            sz[i] = 1;
            sum[i] = S[i];
        }
    }
    int head(int x) {
        if (x == link[x])
            return x;
        return link[x] = head(link[x]);
    }
    bool same(int a, int b) {
        return head(a) == head(b);
    }
    void unite(int a, int b) {
        a = head(a);
        b = head(b);
        if (a == b)
            return;
        if (sz[a] > sz[b])
            swap(a, b);
        sz[a] += sz[b];
        sum[a] += sum[b];
        link[b] = a;
        if (id[lst_added[a]] > id[lst_added[b]])
            lst_added[a] = lst_added[a];
        else
            lst_added[a] = lst_added[b];
    }
};
void dfs(int s, bool x) {
    ans[s] &= x;
    for (auto i : mark[s])
        dfs(i, ans[s]);
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    int n, m;
    cin >> n >> m;
    fill(ans, ans + n + 1, true);
    for (int i = 1; i <= n; i++)
        cin >> S[i];
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    DSU dsu(n+1);
    vector <pair <int, int>> nodes;
    for (int i = 1; i <= n; i++) {
        nodes.push_back({S[i], i});
    }
    sort(nodes.begin(), nodes.end());
    for (int i = 0; i < n; i++)
        id[nodes[i].second] = i;
    for (int i = 0; i < n; i++) {
        for (auto j : adj[nodes[i].second]) {
            if (!vis[j])
                continue;
            int x = dsu.lst_added[dsu.head(j)];
            if (dsu.sum[dsu.head(j)] < nodes[i].first)
                ans[x] = false;
            if (!in_marked[x] && nodes[i].second != x) {
                in_marked[x] = true;
                mark[nodes[i].second].push_back(x);
            }
            dsu.unite(nodes[i].second, j);
        }
        vis[nodes[i].second] = true;
    }
    dfs(nodes[n-1].second, true);
    for (int i = 1; i <= n; i++)
        cout << ans[i];
    cout << '\n';
}

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