Submission #860725

#	Time	Username	Problem	Language	Result	Execution time	Memory
860725		E869120	Stranded Far From Home (BOI22_island)	C++14	Compilation error	0 ms	0 KiB

island

#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);
            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 (stderr)

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:78:20: error: 'class UnionFind' has no member named 'same'
   78 |             if (UF.same(cnts, idx1) == false) { UF.unite(cnts, idx1); G[cnts].push_back(idx1); }
      |                    ^~~~
island.cpp:79:20: error: 'class UnionFind' has no member named 'same'
   79 |             if (UF.same(cnts, idx2) == false) { UF.unite(cnts, idx2); G[cnts].push_back(idx2); }
      |                    ^~~~
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]);
      |                                  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~