oj.uz

Submission #860721

# Submission time Handle Problem Language Result Execution time Memory
860721 2023-10-14T03:25:23 Z E869120 Stranded Far From Home (BOI22_island) C++14
0 / 100
 1000 ms 257176 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) {
    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

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

# Verdict Execution time Memory Grader output
1 Correct 18 ms 148564 KB Output is correct
2 Correct 16 ms 148572 KB Output is correct
3 Correct 16 ms 146524 KB Output is correct
4 Execution timed out 1088 ms 148956 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 148572 KB Output is correct
2 Correct 16 ms 146776 KB Output is correct
3 Correct 331 ms 242580 KB Output is correct
4 Correct 510 ms 212400 KB Output is correct
5 Execution timed out 1067 ms 239980 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 146780 KB Output is correct
2 Execution timed out 1089 ms 257176 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 146640 KB Output is correct
2 Incorrect 356 ms 246004 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 148564 KB Output is correct
2 Correct 16 ms 148572 KB Output is correct
3 Correct 16 ms 146524 KB Output is correct
4 Execution timed out 1088 ms 148956 KB Time limit exceeded
5 Halted 0 ms 0 KB -