oj.uz

Submission #995372

# Submission time Handle Problem Language Result Execution time Memory
995372 2024-06-08T23:48:14 Z asdfgrace Stranded Far From Home (BOI22_island) C++17
10 / 100
 1000 ms 18424 KB 
#include <bits/stdc++.h>
using namespace std;

#define dbg(x) x
#define prt(x) dbg(cerr << x)
#define pv(x) prt(#x << " = " << x << '\n')
#define parr(x) dbg(prt(#x << " = "); for (auto y : x) prt(y << ' '); prt('\n'));
#define parr2d(x) dbg(prt(#x << " = \n"); for (auto y : x) parr(y); prt('\n'));

/*
which ties are possible?
a can convince b if sum(a) > sum(b)
note that nodes are weighted
note that the tie with the strictly least number can't be 1 in the end
one with strictly most can be 1 in the end
how to greedily make 1 the largest?
dfs from the node
and keep adding the smallest adj greedily
and make sure that the size of this color's comp is greater than any other color's comp

subtask 1: brute force
subtask 3: just some weird stuff with set ig
*/

int main() {
  int n, m;
  cin >> n >> m;
  vector<long long> s(n);
  for (int i = 0; i < n; i++) {
    cin >> s[i];
  }
  vector<vector<int>> edges(n);
  for (int i = 0; i < m; i++) {
    int x, y;
    cin >> x >> y;
    x--; y--;
    edges[x].push_back(y);
    edges[y].push_back(x);
  }
  for (int i = 0; i < n; i++) {
    vector<bool> vis(n, false);
    vis[i] = true;
    priority_queue<array<long long, 2>> que;
    que.push({-s[i], i});
    bool ok = true;
    long long tot = s[i];
    while (que.size()) {
      long long sz = -que.top()[0], node = que.top()[1];
      que.pop();
      if (sz > tot) {
        ok = false;
        break;
      }
      if (node != i) {
        tot += sz;
      }
      for (auto next : edges[node]) {
        if (!vis[next]) {
          vis[next] = true;
          que.push({-s[next], next});
        }
      }
    }
    cout << (ok ? 1 : 0);
  }
  cout << '\n';
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 133 ms 348 KB Output is correct
5 Correct 115 ms 348 KB Output is correct
6 Correct 205 ms 344 KB Output is correct
7 Correct 132 ms 348 KB Output is correct
8 Correct 97 ms 348 KB Output is correct
9 Correct 207 ms 604 KB Output is correct
10 Correct 47 ms 344 KB Output is correct
11 Correct 46 ms 344 KB Output is correct
12 Correct 42 ms 484 KB Output is correct
13 Correct 82 ms 348 KB Output is correct
14 Correct 77 ms 564 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Execution timed out 1098 ms 18424 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

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

Subtask #4
0 / 30.0

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

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 133 ms 348 KB Output is correct
5 Correct 115 ms 348 KB Output is correct
6 Correct 205 ms 344 KB Output is correct
7 Correct 132 ms 348 KB Output is correct
8 Correct 97 ms 348 KB Output is correct
9 Correct 207 ms 604 KB Output is correct
10 Correct 47 ms 344 KB Output is correct
11 Correct 46 ms 344 KB Output is correct
12 Correct 42 ms 484 KB Output is correct
13 Correct 82 ms 348 KB Output is correct
14 Correct 77 ms 564 KB Output is correct
15 Correct 1 ms 344 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Execution timed out 1098 ms 18424 KB Time limit exceeded
18 Halted 0 ms 0 KB -