oj.uz

Submission #860722

# Submission time Handle Problem Language Result Execution time Memory
860722 2023-10-14T03:28:32 Z E869120 Stranded Far From Home (BOI22_island) C++14
0 / 100
 976 ms 250216 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 144476 KB Output is correct
2 Correct 16 ms 148572 KB Output is correct
3 Correct 16 ms 146520 KB Output is correct
4 Incorrect 26 ms 148980 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 148568 KB Output is correct
2 Correct 15 ms 146524 KB Output is correct
3 Correct 976 ms 243840 KB Output is correct
4 Correct 743 ms 214224 KB Output is correct
5 Incorrect 903 ms 236380 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 146520 KB Output is correct
2 Incorrect 916 ms 250216 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 146524 KB Output is correct
2 Incorrect 973 ms 239236 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 144476 KB Output is correct
2 Correct 16 ms 148572 KB Output is correct
3 Correct 16 ms 146520 KB Output is correct
4 Incorrect 26 ms 148980 KB Output isn't correct
5 Halted 0 ms 0 KB -