oj.uz

Submission #614240

# Submission time Handle Problem Language Result Execution time Memory
614240 2022-07-30T23:08:43 Z Plurm Stranded Far From Home (BOI22_island) C++11
10 / 100
 1000 ms 15668 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;

int s[200005];
vector<int> g[200005];
int n, m;
bool check(int u) {
  priority_queue<pair<int, int>> pq;
  long long allies = s[u];
  gp_hash_table<int, null_type> alliance;
  alliance.insert(u);
  for (int v : g[u])
    pq.push({-s[v], v});
  while (!pq.empty()) {
    int vnxt = pq.top().second;
    pq.pop();
    if (alliance.find(vnxt) != alliance.end())
      continue;
    if (s[vnxt] <= allies) {
      allies += 1ll * s[vnxt];
      alliance.insert(vnxt);
      for (int v : g[vnxt]) {
        if (alliance.find(v) == alliance.end()) {
          pq.push({-s[v], v});
        }
      }
    } else {
      return false;
    }
  }
  return true;
}
int par[200005];
long long qs[200005];
int suff[200005];
bool dp[200005];
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++) {
    scanf("%d", s + i);
    qs[i] = qs[i - 1] + s[i];
  }
  for (int i = 0; i < m; i++) {
    int u, v;
    scanf("%d%d", &u, &v);
    g[u].push_back(v);
    g[v].push_back(u);
  }
  if (n > 2000) {
    suff[n + 1] = n + 1;
    for (int i = n; i > 0; i--) {
      par[i] = i;
      for (int j : g[i]) {
        if (j < i)
          par[i] = min(par[i], j);
      }
      suff[i] = min(suff[i + 1], par[i]);
    }
    dp[1] = true;
    for (int i = 2; i <= n; i++) {
      dp[i] = (qs[n] - qs[i - 1]) >= s[i - 1] ? dp[i - 1] : false;
    }
    for (int i = 1; i <= n; i++) {
      int x = suff[i];
      while (suff[x] < x)
        x = suff[x];
      if (dp[x])
        printf("1");
      else
        printf("0");
    }
    printf("\n");
  } else {
    for (int i = 1; i <= n; i++) {
      if (check(i))
        printf("1");
      else
        printf("0");
    }
    printf("\n");
  }
  return 0;
}

Compilation message

island.cpp: In function 'int main()':
island.cpp:40:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |   scanf("%d%d", &n, &m);
      |   ~~~~~^~~~~~~~~~~~~~~~
island.cpp:42:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 |     scanf("%d", s + i);
      |     ~~~~~^~~~~~~~~~~~~
island.cpp:47:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 |     scanf("%d%d", &u, &v);
      |     ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 2 ms 5068 KB Output is correct
4 Correct 253 ms 5144 KB Output is correct
5 Correct 215 ms 5156 KB Output is correct
6 Correct 373 ms 5144 KB Output is correct
7 Correct 260 ms 5076 KB Output is correct
8 Correct 194 ms 5152 KB Output is correct
9 Correct 279 ms 5148 KB Output is correct
10 Correct 112 ms 5156 KB Output is correct
11 Correct 95 ms 5156 KB Output is correct
12 Correct 156 ms 5152 KB Output is correct
13 Correct 188 ms 5152 KB Output is correct
14 Correct 143 ms 5156 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Execution timed out 1086 ms 15668 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Execution timed out 1096 ms 15456 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Incorrect 126 ms 15548 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 2 ms 5068 KB Output is correct
4 Correct 253 ms 5144 KB Output is correct
5 Correct 215 ms 5156 KB Output is correct
6 Correct 373 ms 5144 KB Output is correct
7 Correct 260 ms 5076 KB Output is correct
8 Correct 194 ms 5152 KB Output is correct
9 Correct 279 ms 5148 KB Output is correct
10 Correct 112 ms 5156 KB Output is correct
11 Correct 95 ms 5156 KB Output is correct
12 Correct 156 ms 5152 KB Output is correct
13 Correct 188 ms 5152 KB Output is correct
14 Correct 143 ms 5156 KB Output is correct
15 Correct 3 ms 4948 KB Output is correct
16 Correct 2 ms 4948 KB Output is correct
17 Execution timed out 1086 ms 15668 KB Time limit exceeded
18 Halted 0 ms 0 KB -