oj.uz

Submission #614251

# Submission time Handle Problem Language Result Execution time Memory
614251 2022-07-30T23:39:01 Z Plurm Stranded Far From Home (BOI22_island) C++11
10 / 100
 387 ms 16224 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];
int bck[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;
    bck[1] = 1;
    for (int i = 2; i <= n; i++) {
      bck[i] = i;
      if (suff[i] != i) {
        bck[i] = bck[suff[i]];
        dp[i] = dp[bck[i]];
      }
      dp[i] |= (qs[n] - qs[i - 1]) >= s[i - 1] ? dp[i - 1] : false;
    }
    for (int i = 1; i <= n; i++) {
      if (dp[i])
        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:41:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |   scanf("%d%d", &n, &m);
      |   ~~~~~^~~~~~~~~~~~~~~~
island.cpp:43:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |     scanf("%d", s + i);
      |     ~~~~~^~~~~~~~~~~~~
island.cpp:48:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |     scanf("%d%d", &u, &v);
      |     ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
10.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 Correct 2 ms 4948 KB Output is correct
4 Correct 258 ms 5144 KB Output is correct
5 Correct 245 ms 5236 KB Output is correct
6 Correct 387 ms 5140 KB Output is correct
7 Correct 302 ms 5148 KB Output is correct
8 Correct 200 ms 5140 KB Output is correct
9 Correct 300 ms 5192 KB Output is correct
10 Correct 97 ms 5076 KB Output is correct
11 Correct 97 ms 5148 KB Output is correct
12 Correct 157 ms 5156 KB Output is correct
13 Correct 167 ms 5076 KB Output is correct
14 Correct 152 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 3 ms 4948 KB Output is correct
3 Incorrect 135 ms 16220 KB Output isn't correct
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 Incorrect 122 ms 16224 KB Output isn't correct
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 148 ms 16220 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.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 Correct 2 ms 4948 KB Output is correct
4 Correct 258 ms 5144 KB Output is correct
5 Correct 245 ms 5236 KB Output is correct
6 Correct 387 ms 5140 KB Output is correct
7 Correct 302 ms 5148 KB Output is correct
8 Correct 200 ms 5140 KB Output is correct
9 Correct 300 ms 5192 KB Output is correct
10 Correct 97 ms 5076 KB Output is correct
11 Correct 97 ms 5148 KB Output is correct
12 Correct 157 ms 5156 KB Output is correct
13 Correct 167 ms 5076 KB Output is correct
14 Correct 152 ms 5156 KB Output is correct
15 Correct 3 ms 4948 KB Output is correct
16 Correct 3 ms 4948 KB Output is correct
17 Incorrect 135 ms 16220 KB Output isn't correct
18 Halted 0 ms 0 KB -