Submission #860722

#	Time	Username	Problem	Language	Result	Execution time	Memory
860722		E869120	Stranded Far From Home (BOI22_island)	C++14	0 / 100	976 ms	250216 KiB

island

#include <bits/stdc++.h>
using namespace std;

long long N, S[1 << 19];
long long M, A[1 << 19], B[1 << 19];
long long Current;
long long Color[32][1 << 19];
long long Nexts[32][1 << 18];
long long Costs[32][1 << 19];
vector<int> G[1 << 19];

void dfs(int dim, int pos) {
    Color[dim][pos] = Current;
    Costs[dim][Current] += S[pos];
    for (int to : G[pos]) {
        if (Color[dim][to] != 0) continue;
        dfs(dim, to);
    }
}

int get_id(long long x) {
    if (x == 0) return 0;
    for (int i = 0; i <= 29; i++) {
        if ((1LL << i) <= x && x < (1LL << (i + 1))) return i + 1;
    }
    return 31;
}

bool solve(int pos) {
    for (int lev = 0; lev <= 31; lev++) {
        long long col = Color[lev][pos];
        long long cur = Costs[lev][col];
        long long nex = Nexts[lev][col];
        if (nex == (1LL << 60)) return true;
        if (cur < nex) return false;
    }
    return true;
}

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. DFS
    for (int d = 0; d <= 31; d++) {
        for (int i = 1; i <= N; i++) G[i].clear();
        for (int i = 1; i <= N; i++) Nexts[d][i] = (1LL << 60);
        for (int i = 1; i <= M; i++) {
            if (S[A[i]] >= (1LL << d) || S[B[i]] >= (1LL << d)) continue;
            G[A[i]].push_back(B[i]);
            G[B[i]].push_back(A[i]);
        }
        Current = 0;
        for (int i = 1; i <= N; i++) {
            if (Color[d][i] != 0) continue;
            Current += 1;
            dfs(d, i);
        }
        for (int i = 1; i <= M; i++) {
            int col1 = Color[d][A[i]];
            int col2 = Color[d][B[i]];
            if (col1 == col2) continue;
            Nexts[d][col1] = min(Nexts[d][col1], max(S[A[i]], S[B[i]]));
            Nexts[d][col2] = min(Nexts[d][col2], max(S[A[i]], S[B[i]]));
        }
    }

    // Step 3. Query
    for (int i = 1; i <= N; i++) {
        bool ret = solve(i);
        if (ret == true) printf("1");
        else printf("0");
    }
    printf("\n");
    return 0;
}

Compilation message (stderr)

island.cpp: In function 'int main()':
island.cpp:42:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 |     scanf("%lld%lld", &N, &M);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~
island.cpp:43:39: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |     for (int i = 1; i <= N; i++) scanf("%lld", &S[i]);
      |                                  ~~~~~^~~~~~~~~~~~~~~
island.cpp:44:39: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   44 |     for (int i = 1; i <= M; i++) scanf("%lld%lld", &A[i], &B[i]);
      |                                  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 15
• Subtask 4: 0 / 30
• Subtask 5: 0 / 35