oj.uz

Submission #1016424

# Submission time Handle Problem Language Result Execution time Memory
1016424 2024-07-08T05:03:14 Z asdfgrace Stranded Far From Home (BOI22_island) C++17
20 / 100
 205 ms 37972 KB 
#include <bits/stdc++.h>
using namespace std;

#define dbg(x) //x
#define prt(x) dbg(cerr << x)
#define pv(x) dbg(cerr << #x << " = " << x << '\n')
#define pv2(x) dbg(cerr << #x << " = " << x.first << ',' << x.second << '\n')
#define parr(x) dbg(prt(#x << " = { "); for (auto y : x) prt(y << ' '); prt("}\n");)
#define parr2(x) dbg(prt(#x << " = { "); for (auto [y, z] : x) prt(y << ',' << z << "  "); prt("}\n");)
#define parr2d(x) dbg(prt(#x << ":\n"); for (auto arr : x) {parr(arr);} prt('\n'));
#define parr2d2(x) dbg(prt(#x << ":\n"); for (auto arr : x) {parr2(arr);} prt('\n'));

int main() {
  ios::sync_with_stdio(0); cin.tie(0);
  int n, m;
  cin >> n >> m;
  vector<long long> s(n);
  for (int i = 0; i < n; i++) {
    cin >> s[i];
  }
  bool inc = false;
  for (int i = 0; i < n - 1; i++) {
    if (s[i + 1] > s[i]) {
      inc = true;
    }
  }
  bool dif1 = true;
  vector<vector<int>> edges(n);
  for (int i = 0; i < m; i++) {
    int x, y;
    cin >> x >> y;
    x--; y--;
    if (abs(x - y) > 1) dif1 = false;
    edges[x].push_back(y);
    edges[y].push_back(x);
  }
  if (n <= 2000 && m <= 2000) {
    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';
  } else if (m == n - 1 && !inc) {
    vector<bool> ok(n, true);
    vector<long long> sum = s;
    function<void(int, int)> dfs1 = [&] (int node, int par) {
      for (auto next : edges[node]) {
        if (next != par) {
          dfs1(next, node);
          sum[node] += sum[next];
        }
      }
    };
    dfs1(0, 0);
    function<void(int, int)> dfs2 = [&] (int node, int par) {
      if (node != 0) {
        ok[node] = ok[par];
        if (s[par] > sum[node]) {
          ok[node] = false;
        }
      }
      for (auto next : edges[node]) {
        if (next != par) {
          dfs2(next, node);
        }
      }
    };
    dfs2(0, 0);
    for (int i = 0; i < n; i++) {
      cout << (ok[i] ? 1 : 0);
    }
    cout << '\n';
  } else if (dif1) {
    /*
    other way around: look for all pairs of walls
    so that sum between the walls < min val of the 2 walls
    note: may be single elem restricting lb/rb
    so if this elem > sum of pref, nothing before it works
    or if elem > sum of suf, nothing after it works
    after finding these
    for every l wall
    what's max r wall
    within the range of r so that sum(l+1...r-1) < a[l]
    (mxr = lower_bound(a.begin(), a.end(), pref[l] + a[l]))
    (mxr maybe not monotonic - use segtree?)
    (finding max ind)
    (upd segtree and process inds in order of r)
    sum(l+1...r-1) < a[r] --> rightmost in [l+1,mxr] so that mnl[r] <= l
    so max segtree
    when time comes, st[i] = i
    process l in order
    update the segtree
    before processing each l
    update each segtree index
    so that mnl[r] <= l
    */
    vector<long long> ps = s;
    for (int i = 1; i < n; i++) {
      ps[i] += ps[i - 1];
    }
    vector<bool> ok(n, true);
    for (int i = n - 1; i > 0; i--) {
      if (s[i] > ps[i - 1]) {
        for (int j = 0; j < i; j++) {
          ok[j] = false;
        }
        break;
      }
    }
    for (int i = 0; i < n - 1; i++) {
      if (s[i] > ps[n - 1] - ps[i]) {
        for (int j = i + 1; j < n; j++) {
          ok[j] = false;
        }
        break;
      }
    }
    parr(ok);
    vector<int> mxr(n), mnl(n);
    for (int i = 0; i < n; i++) {
      mxr[i] = lower_bound(ps.begin(), ps.end(), ps[i] + s[i]) - ps.begin();
      mnl[i] = upper_bound(ps.begin(), ps.end(), ps[i] - 2 * s[i]) - ps.begin() - 1;
      mxr[i] = min(mxr[i], n - 1);
      mnl[i] = max(mnl[i], 0);
    }
    parr(mnl); parr(mxr);
    vector<int> ord(n);
    iota(ord.begin(), ord.end(), 0);
    sort(ord.begin(), ord.end(), [&] (int x, int y) {
      return mnl[x] < mnl[y];
    });
    vector<int> st(2 * n, -1);
    function<void(int, int)> upd = [&] (int ind, int val) {
      ind += n; st[ind] = val;
      for (int i = ind / 2; i > 0; i /= 2) {
        st[i] = max(st[i * 2], st[i * 2 + 1]);
      }
    };
    function<int(int, int)> quer = [&] (int l, int r) {
      l += n; r += n;
      int mx = -1;
      while (l <= r) {
        if (l % 2 == 1) mx = max(mx, st[l++]);
        if (r % 2 == 0) mx = max(mx, st[r--]);
        l /= 2; r /= 2;
      }
      return mx;
    };
    int it = 0;
    vector<int> stat(n, 0), enat(n, 0);
    for (int l = 0; l < n; l++) {
      pv(l);
      while (it < n && mnl[ord[it]] <= l) {
        upd(ord[it], ord[it]);
        it++;
      }
      if (mxr[l] >= l + 1) {
        int best = quer(l + 1, mxr[l]);
        pv(best);
        if (best != -1) {
          stat[l + 1]++;
          enat[best]++;
        }
      }
    }
    int cur = 0;
    for (int i = 0; i < n; i++) {
      cur -= enat[i];
      cur += stat[i];
      if (cur > 0) ok[i] = false;
    }
    for (int i = 0; i < n; i++) {
      cout << (ok[i] ? '1' : '0');
    }
    cout << '\n';
  }
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 132 ms 604 KB Output is correct
5 Correct 114 ms 604 KB Output is correct
6 Correct 205 ms 572 KB Output is correct
7 Correct 151 ms 588 KB Output is correct
8 Correct 91 ms 568 KB Output is correct
9 Correct 203 ms 616 KB Output is correct
10 Correct 47 ms 604 KB Output is correct
11 Correct 45 ms 600 KB Output is correct
12 Correct 41 ms 604 KB Output is correct
13 Correct 82 ms 604 KB Output is correct
14 Correct 73 ms 600 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 79 ms 26720 KB Output is correct
4 Correct 71 ms 25168 KB Output is correct
5 Correct 78 ms 18512 KB Output is correct
6 Correct 85 ms 19028 KB Output is correct
7 Correct 77 ms 19092 KB Output is correct
8 Correct 85 ms 19252 KB Output is correct
9 Correct 71 ms 19036 KB Output is correct
10 Correct 59 ms 19044 KB Output is correct
11 Correct 58 ms 18752 KB Output is correct
12 Correct 98 ms 17772 KB Output is correct
13 Correct 79 ms 36436 KB Output is correct
14 Correct 81 ms 36436 KB Output is correct
15 Correct 82 ms 37972 KB Output is correct
16 Correct 66 ms 36944 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 90 ms 24352 KB Output isn't correct
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 Incorrect 62 ms 17360 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 132 ms 604 KB Output is correct
5 Correct 114 ms 604 KB Output is correct
6 Correct 205 ms 572 KB Output is correct
7 Correct 151 ms 588 KB Output is correct
8 Correct 91 ms 568 KB Output is correct
9 Correct 203 ms 616 KB Output is correct
10 Correct 47 ms 604 KB Output is correct
11 Correct 45 ms 600 KB Output is correct
12 Correct 41 ms 604 KB Output is correct
13 Correct 82 ms 604 KB Output is correct
14 Correct 73 ms 600 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 79 ms 26720 KB Output is correct
18 Correct 71 ms 25168 KB Output is correct
19 Correct 78 ms 18512 KB Output is correct
20 Correct 85 ms 19028 KB Output is correct
21 Correct 77 ms 19092 KB Output is correct
22 Correct 85 ms 19252 KB Output is correct
23 Correct 71 ms 19036 KB Output is correct
24 Correct 59 ms 19044 KB Output is correct
25 Correct 58 ms 18752 KB Output is correct
26 Correct 98 ms 17772 KB Output is correct
27 Correct 79 ms 36436 KB Output is correct
28 Correct 81 ms 36436 KB Output is correct
29 Correct 82 ms 37972 KB Output is correct
30 Correct 66 ms 36944 KB Output is correct
31 Correct 0 ms 344 KB Output is correct
32 Incorrect 90 ms 24352 KB Output isn't correct
33 Halted 0 ms 0 KB -