oj.uz

Submission #847345

# Submission time Handle Problem Language Result Execution time Memory
847345 2023-09-09T13:52:24 Z ArashJafariyan Stranded Far From Home (BOI22_island) C++17
0 / 100
 173 ms 30988 KB 
#include <bits/stdc++.h>
using ll = long long;

#define pb push_back

const int N = 2e5 + 4;

int n, m, st[N], a[N], b[N], idx[N], par[N];
ll sum[N];
char ans[N];
std::vector<int> vset[N];

bool cmp(int i, int j) {
    int x = std::max(st[a[i]], st[b[i]]);
    int y = std::max(st[a[j]], st[b[j]]);
    return x < y;
}

int gr(int v) {
    std::stack<int> s;
    s.push(v);
    while (par[s.top()] != s.top()) {
        s.push(par[s.top()]);
    }

    int ret = s.top();
    while (!s.empty()) {
        par[s.top()] = ret;
        s.pop();
    }
    return ret;
}

void mrg(int v, int u, int w) {
    v = gr(v);
    u = gr(u);
    if (v == u) {
        return;
    }
    if (sum[v] > sum[u]) {
        std::swap(v, u);
    }

    bool b = sum[v] < w;
    for (int x : vset[v]) {
        vset[u].pb(v);
        if (b) {
            ans[x] = '0';
        }
    }
    sum[u] += sum[v];
    par[v] = u;
    return;
}

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

    std::cin >> n >> m;
    for (int i = 0; i < n; ++i) {
        std::cin >> sum[i];
        st[i] = sum[i];
        vset[i].pb(i);
        ans[i] = '1';
        par[i] = i;
    }
    for (int i = 0; i < m; ++i) {
        std::cin >> a[i] >> b[i];
        --a[i], --b[i];
        idx[i] = i;
    }
    std::sort(idx, idx + m, cmp); 
    
    for (int i = 0; i < m; ++i) {
        int j = idx[i];
        int w = std::max(st[a[j]], st[b[j]]);
        mrg(a[j], b[j], w);
    }
    for (int i = 0; i < n; ++i) {
        std::cout << ans[i];
    }
    return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8792 KB Output is correct
2 Correct 2 ms 8792 KB Output is correct
3 Correct 2 ms 8796 KB Output is correct
4 Correct 3 ms 8792 KB Output is correct
5 Correct 3 ms 8792 KB Output is correct
6 Correct 2 ms 8996 KB Output is correct
7 Correct 2 ms 8792 KB Output is correct
8 Correct 2 ms 8796 KB Output is correct
9 Incorrect 3 ms 8792 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8792 KB Output is correct
2 Correct 2 ms 8792 KB Output is correct
3 Correct 110 ms 22824 KB Output is correct
4 Incorrect 128 ms 30988 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8792 KB Output is correct
2 Incorrect 173 ms 28996 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8792 KB Output is correct
2 Incorrect 131 ms 24596 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8792 KB Output is correct
2 Correct 2 ms 8792 KB Output is correct
3 Correct 2 ms 8796 KB Output is correct
4 Correct 3 ms 8792 KB Output is correct
5 Correct 3 ms 8792 KB Output is correct
6 Correct 2 ms 8996 KB Output is correct
7 Correct 2 ms 8792 KB Output is correct
8 Correct 2 ms 8796 KB Output is correct
9 Incorrect 3 ms 8792 KB Output isn't correct
10 Halted 0 ms 0 KB -