oj.uz

Submission #614234

# Submission time Handle Problem Language Result Execution time Memory
614234 2022-07-30T22:48:30 Z Plurm Stranded Far From Home (BOI22_island) C++11
10 / 100
 903 ms 20380 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 main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++) {
    scanf("%d", 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) {
    int lo = 1;
    int hi = n;
    int mid;
    while (lo < hi) {
      mid = (lo + hi) / 2;
      if (check(mid)) {
        lo = mid + 1;
      } else {
        hi = mid;
      }
    }
    if (lo == n && check(lo)) {
      for (int i = 1; i <= n; i++)
        printf("1");
      printf("\n");
    } else {
      for (int i = 1; i < lo; i++)
        printf("1");
      for (int i = lo; i <= n; i++)
        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:36:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |   scanf("%d%d", &n, &m);
      |   ~~~~~^~~~~~~~~~~~~~~~
island.cpp:38:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |     scanf("%d", s + i);
      |     ~~~~~^~~~~~~~~~~~~
island.cpp:42:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 |     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 2 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 251 ms 5108 KB Output is correct
5 Correct 216 ms 5116 KB Output is correct
6 Correct 410 ms 5076 KB Output is correct
7 Correct 268 ms 5108 KB Output is correct
8 Correct 203 ms 5104 KB Output is correct
9 Correct 286 ms 5108 KB Output is correct
10 Correct 98 ms 5076 KB Output is correct
11 Correct 94 ms 5120 KB Output is correct
12 Correct 167 ms 5120 KB Output is correct
13 Correct 183 ms 5132 KB Output is correct
14 Correct 148 ms 5076 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 470 ms 20380 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Incorrect 299 ms 20272 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 903 ms 20328 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 2 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 251 ms 5108 KB Output is correct
5 Correct 216 ms 5116 KB Output is correct
6 Correct 410 ms 5076 KB Output is correct
7 Correct 268 ms 5108 KB Output is correct
8 Correct 203 ms 5104 KB Output is correct
9 Correct 286 ms 5108 KB Output is correct
10 Correct 98 ms 5076 KB Output is correct
11 Correct 94 ms 5120 KB Output is correct
12 Correct 167 ms 5120 KB Output is correct
13 Correct 183 ms 5132 KB Output is correct
14 Correct 148 ms 5076 KB Output is correct
15 Correct 3 ms 4948 KB Output is correct
16 Correct 3 ms 4948 KB Output is correct
17 Incorrect 470 ms 20380 KB Output isn't correct
18 Halted 0 ms 0 KB -