oj.uz

Submission #860726

# Submission time Handle Problem Language Result Execution time Memory
860726 2023-10-14T04:11:41 Z E869120 Stranded Far From Home (BOI22_island) C++14
25 / 100
 185 ms 95216 KB 
#include <bits/stdc++.h>
using namespace std;

class UnionFind {
    public:
    vector<long long> par;
    vector<long long> sum;

    void init(int sz) {
        par.resize(sz, -1);
        sum.resize(sz, 0);
    }

    void touroku(int pos, long long x) {
        sum[pos] += x;
    }

    int root(int pos) {
        if (par[pos] == -1) return pos;
        par[pos] = root(par[pos]);
        return par[pos];
    }

    void unite(int u, int v) {
        u = root(u); v = root(v);
        if (u == v) return;
        if (u > v) swap(u, v);
        sum[v] += sum[u];
        par[u] = v; // Add edge v -> u
    }

    bool same(int u, int v) {
        if (root(u) == root(v)) return true;
        return false;
    }
};

long long N, S[1 << 19];
long long M, A[1 << 19], B[1 << 19];
bool Eval[1 << 19];
vector<long long> Zahyou;
vector<pair<int, int>> Edge[1 << 19];
vector<int> G[1 << 19];
UnionFind UF;

void dfs(int pos) {
    for (int to : G[pos]) Eval[to] |= Eval[pos];
    for (int to : G[pos]) dfs(to);
}

int main() {
    // Step 1. Input
    scanf("%lld%lld", &N, &M);
    for (int i = 1; i <= N; i++) scanf("%lld", &S[i]);
    for (int i = 1; i <= M; i++) scanf("%lld%lld", &A[i], &B[i]);

    // Step 2. Compression
    for (int i = 1; i <= N; i++) Zahyou.push_back(S[i]);
    sort(Zahyou.begin(), Zahyou.end());
    Zahyou.erase(unique(Zahyou.begin(), Zahyou.end()), Zahyou.end());
    
    // Step 3. Add Edges
    for (int i = 1; i <= M; i++) {
        int pos1 = lower_bound(Zahyou.begin(), Zahyou.end(), max(S[A[i]], S[B[i]])) - Zahyou.begin();
        Edge[pos1].push_back(make_pair(A[i], B[i]));
    }

    // Step 4. Union Find
    UF.init(2 * N + 2);
    for (int i = 1; i <= N; i++) UF.touroku(i, S[i]);
    int cnts = N;
    for (int i = 0; i < Zahyou.size(); i++) {
        for (pair<int, int> e : Edge[i]) {
            int idx1 = UF.root(e.first);
            int idx2 = UF.root(e.second);
            if (UF.sum[idx1] < Zahyou[i]) Eval[idx1] = true;
            if (UF.sum[idx2] < Zahyou[i]) Eval[idx2] = true;
        }
        for (pair<int, int> e : Edge[i]) {
            cnts += 1;
            int idx1 = UF.root(e.first);
            int idx2 = UF.root(e.second);
            if (UF.same(cnts, idx1) == false) { UF.unite(cnts, idx1); G[cnts].push_back(idx1); }
            if (UF.same(cnts, idx2) == false) { UF.unite(cnts, idx2); G[cnts].push_back(idx2); }
        }
    }

    // Step 5. DFS
    dfs(cnts);
    for (int i = 1; i <= N; i++) {
        if (Eval[i] == false) printf("1");
        else printf("0");
    }
    printf("\n");
    return 0;
}

Compilation message

island.cpp: In function 'int main()':
island.cpp:72:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |     for (int i = 0; i < Zahyou.size(); i++) {
      |                     ~~^~~~~~~~~~~~~~~
island.cpp:53:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   53 |     scanf("%lld%lld", &N, &M);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~
island.cpp:54:39: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   54 |     for (int i = 1; i <= N; i++) scanf("%lld", &S[i]);
      |                                  ~~~~~^~~~~~~~~~~~~~~
island.cpp:55:39: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   55 |     for (int i = 1; i <= M; i++) scanf("%lld%lld", &A[i], &B[i]);
      |                                  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 31324 KB Output is correct
2 Correct 6 ms 31392 KB Output is correct
3 Correct 5 ms 27228 KB Output is correct
4 Runtime error 30 ms 63528 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 31324 KB Output is correct
2 Correct 6 ms 27228 KB Output is correct
3 Correct 134 ms 53236 KB Output is correct
4 Correct 90 ms 47280 KB Output is correct
5 Correct 141 ms 49128 KB Output is correct
6 Correct 134 ms 49164 KB Output is correct
7 Correct 151 ms 49728 KB Output is correct
8 Correct 102 ms 47168 KB Output is correct
9 Correct 114 ms 48328 KB Output is correct
10 Correct 99 ms 53312 KB Output is correct
11 Correct 84 ms 53316 KB Output is correct
12 Correct 100 ms 47292 KB Output is correct
13 Correct 88 ms 47168 KB Output is correct
14 Correct 106 ms 47140 KB Output is correct
15 Correct 170 ms 58168 KB Output is correct
16 Correct 91 ms 57788 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 27228 KB Output is correct
2 Correct 165 ms 49656 KB Output is correct
3 Correct 161 ms 49392 KB Output is correct
4 Correct 93 ms 47164 KB Output is correct
5 Correct 86 ms 47244 KB Output is correct
6 Correct 185 ms 49784 KB Output is correct
7 Correct 150 ms 58116 KB Output is correct
8 Correct 153 ms 58112 KB Output is correct
9 Correct 102 ms 57804 KB Output is correct
10 Correct 95 ms 47168 KB Output is correct
11 Correct 99 ms 47348 KB Output is correct

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 27232 KB Output is correct
2 Runtime error 138 ms 95216 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 31324 KB Output is correct
2 Correct 6 ms 31392 KB Output is correct
3 Correct 5 ms 27228 KB Output is correct
4 Runtime error 30 ms 63528 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -