oj.uz

Submission #614231

# Submission time Handle Problem Language Result Execution time Memory
614231 2022-07-30T22:45:31 Z Plurm Stranded Far From Home (BOI22_island) C++11
10 / 100
 1000 ms 21552 KB 
#include <bits/stdc++.h>
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];
  set<int> alliance = {u};
  for (int v : g[u])
    pq.push({-s[v], v});
  while (!pq.empty()) {
    int vnxt = pq.top().second;
    pq.pop();
    if (alliance.count(vnxt))
      continue;
    if (s[vnxt] <= allies) {
      allies += 1ll * s[vnxt];
      alliance.insert(vnxt);
      for (int v : g[vnxt]) {
        if (!alliance.count(v)) {
          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 (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 + 1; 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:33:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |   scanf("%d%d", &n, &m);
      |   ~~~~~^~~~~~~~~~~~~~~~
island.cpp:35:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   35 |     scanf("%d", s + i);
      |     ~~~~~^~~~~~~~~~~~~
island.cpp:39:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   39 |     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 758 ms 5128 KB Output is correct
5 Correct 755 ms 5188 KB Output is correct
6 Correct 958 ms 5152 KB Output is correct
7 Correct 731 ms 5164 KB Output is correct
8 Correct 530 ms 5076 KB Output is correct
9 Correct 719 ms 5264 KB Output is correct
10 Correct 353 ms 5192 KB Output is correct
11 Correct 328 ms 5204 KB Output is correct
12 Correct 452 ms 5184 KB Output is correct
13 Correct 616 ms 5168 KB Output is correct
14 Correct 396 ms 5204 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4960 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Execution timed out 1078 ms 21552 KB Time limit exceeded
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 813 ms 21460 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4908 KB Output is correct
2 Execution timed out 1079 ms 21440 KB Time limit exceeded
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 758 ms 5128 KB Output is correct
5 Correct 755 ms 5188 KB Output is correct
6 Correct 958 ms 5152 KB Output is correct
7 Correct 731 ms 5164 KB Output is correct
8 Correct 530 ms 5076 KB Output is correct
9 Correct 719 ms 5264 KB Output is correct
10 Correct 353 ms 5192 KB Output is correct
11 Correct 328 ms 5204 KB Output is correct
12 Correct 452 ms 5184 KB Output is correct
13 Correct 616 ms 5168 KB Output is correct
14 Correct 396 ms 5204 KB Output is correct
15 Correct 2 ms 4960 KB Output is correct
16 Correct 2 ms 4948 KB Output is correct
17 Execution timed out 1078 ms 21552 KB Time limit exceeded
18 Halted 0 ms 0 KB -