oj.uz

Submission #860724

# Submission time Handle Problem Language Result Execution time Memory
860724 2023-10-14T04:10:10 Z E869120 Stranded Far From Home (BOI22_island) C++14
25 / 100
 184 ms 99180 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
    }
};

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);
            UF.unite(cnts, idx1); G[cnts].push_back(idx1);
            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:67:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |     for (int i = 0; i < Zahyou.size(); i++) {
      |                     ~~^~~~~~~~~~~~~~~
island.cpp:48:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |     scanf("%lld%lld", &N, &M);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~
island.cpp:49:39: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   49 |     for (int i = 1; i <= N; i++) scanf("%lld", &S[i]);
      |                                  ~~~~~^~~~~~~~~~~~~~~
island.cpp:50:39: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   50 |     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 31168 KB Output is correct
3 Correct 5 ms 27224 KB Output is correct
4 Runtime error 35 ms 63488 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 31320 KB Output is correct
2 Correct 5 ms 27228 KB Output is correct
3 Correct 144 ms 57056 KB Output is correct
4 Correct 108 ms 50108 KB Output is correct
5 Correct 139 ms 52672 KB Output is correct
6 Correct 140 ms 53692 KB Output is correct
7 Correct 166 ms 54208 KB Output is correct
8 Correct 114 ms 51516 KB Output is correct
9 Correct 118 ms 52580 KB Output is correct
10 Correct 96 ms 56828 KB Output is correct
11 Correct 90 ms 56896 KB Output is correct
12 Correct 100 ms 50364 KB Output is correct
13 Correct 94 ms 49968 KB Output is correct
14 Correct 92 ms 50400 KB Output is correct
15 Correct 144 ms 62728 KB Output is correct
16 Correct 96 ms 61404 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 160 ms 53488 KB Output is correct
3 Correct 160 ms 53812 KB Output is correct
4 Correct 95 ms 51520 KB Output is correct
5 Correct 91 ms 49980 KB Output is correct
6 Correct 184 ms 54104 KB Output is correct
7 Correct 167 ms 62632 KB Output is correct
8 Correct 150 ms 62564 KB Output is correct
9 Correct 119 ms 61628 KB Output is correct
10 Correct 103 ms 51008 KB Output is correct
11 Correct 104 ms 50364 KB Output is correct

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 27224 KB Output is correct
2 Runtime error 127 ms 99180 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 31168 KB Output is correct
3 Correct 5 ms 27224 KB Output is correct
4 Runtime error 35 ms 63488 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -