oj.uz

답안 #1025133

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1025133 2024-07-16T16:23:07 Z overwatch9 Stranded Far From Home (BOI22_island) C++17
0 / 100
 3 ms 5144 KB 
#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.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4956 KB Output is correct
2 Correct 3 ms 4956 KB Output is correct
3 Incorrect 2 ms 4956 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4956 KB Output is correct
2 Incorrect 2 ms 4956 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 4952 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 5144 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4956 KB Output is correct
2 Correct 3 ms 4956 KB Output is correct
3 Incorrect 2 ms 4956 KB Output isn't correct
4 Halted 0 ms 0 KB -