Submission #860721

#	Time	Username	Problem	Language	Result	Execution time	Memory
860721		E869120	Stranded Far From Home (BOI22_island)	C++14	0 / 100	1089 ms	257176 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) {
    long long cur = S[pos];
    while (true) {
        int idx = get_id(cur + 1LL) - 1LL; if (cur == S[pos]) idx = 0;
        long long col = Color[idx][pos];
        long long nex = Nexts[idx][col];
        // cout << pos << " " << cur << " " << idx << " " << col << " " << nex << endl;
        if (nex == (1LL << 60)) return true;
        if (cur < nex) return false;
        cur = Costs[get_id(nex)][Color[get_id(nex)][pos]];
    }
}

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:44:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   44 |     scanf("%lld%lld", &N, &M);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~
island.cpp:45:39: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   45 |     for (int i = 1; i <= N; i++) scanf("%lld", &S[i]);
      |                                  ~~~~~^~~~~~~~~~~~~~~
island.cpp:46:39: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   46 |     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