Submission #1025133

#	Time	Username	Problem	Language	Result	Execution time	Memory
1025133		overwatch9	Stranded Far From Home (BOI22_island)	C++17	0 / 100	3 ms	5144 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];
int state[maxn];
bool ans[maxn];
struct DSU {
    vector <int> link, sz;
    vector <ll> sum;
    DSU (int s) {
        link = sz = vector <int> (s+1);
        sum = vector <ll> (s+1);
        for (int i = 1; i <= s; i++) {
            link[i] = i;
            sz[i] = 1;
            sum[i] = S[i];
        }
    }
    int head(int x) {
        while (x != link[x])
            x = link[x];
        return 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 (sz[a] > sz[b])
            swap(a, b);
        sz[a] += sz[b];
        sum[a] += sum[b];
        link[b] = a;
    }
};
int main() {
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    int n, m;
    cin >> n >> m;
    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());
    vector <int> nxt(n);
    for (int i = n-1; i >= 0; i--) {
        if (i+1 < n && nodes[i].first == nodes[i+1].first)
            nxt[i] = nxt[i+1];
        else if (i+1 < n)
            nxt[i] = nodes[i+1].first;
    }
    for (int i = 0; i < n; i++) {
        if (i > 0 && nodes[i-1].first == nodes[i].first)
            continue;
        vector <int> nodes2;
        nodes2.push_back(nodes[i].second);
        ll sum = nodes[i].first;
        for (int j = i+1; j < n; j++) {
            if (nodes[j].first != nodes[i].first)
                break;
            dsu.unite(nodes[j].second, nodes[i].second);
            nodes2.push_back(nodes[j].second);
            sum += nodes[j].first;
        }
        bool fine = false;
        for (auto j : nodes2) {
            for (auto k : adj[j]) {
                if (sum >= S[k])
                    fine = true;
            }
        }
        for (auto j : nodes2) {
            if (fine)
                state[j] = 1;
            else
                state[j] = -1;
        }
    }
    for (int i = n-1; i >= 0; i--) {
        if (i < n-1 && nodes[i+1].first == nodes[i].first)
            continue;
        if (state[nodes[i].second] == -1)
            continue;
        vector <int> nodes2;
        nodes2.push_back(nodes[i].second);
        for (int j = i-1; j >= 0; j--) {
            if (nodes[j].first != nodes[i].first)
                break;
            nodes2.push_back(nodes[j].second);
        }
        bool fine = false;
        if (i == n-1)
            fine = true;
        for (auto j : nodes2) {
            for (auto k : adj[j]) {
                fine |= ans[k];
            }
        }
        for (auto j : nodes2)
            ans[j] = fine;
    }
    for (int i = 1; i <= n; i++)
        cout << ans[i];
    cout << '\n';
}

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