oj.uz

Submission #284260

# Submission time Handle Problem Language Result Execution time Memory
284260 2020-08-27T06:00:10 Z 김동현(#5767) Aesthetic (NOI20_aesthetic) C++17
0 / 100
 863 ms 49728 KB 
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;

using vint = vector<int>;
using vll = vector<ll>;
using vld = vector<ld>;
using vpii = vector<pii>;
using vpil = vector<pil>;
using vpli = vector<pli>;
using vpll = vector<pll>;

#define x first
#define y second
#define all(v) v.begin(),v.end()

const ll INF = ll(1e18);

namespace Seg {
  const int sz = 524288;
  vll d(2 * sz, INF);
  
  void u(int s, int e, ll v) {
    for(s += sz, e += sz; s <= e; s /= 2, e /= 2) {
      if(s & 1) d[s++] = min(d[s], v);
      if(~e & 1) d[e--] = min(d[e], v);
    }
  }

  ll g(int x) {
    ll r = INF;
    for(x += sz; x; x /= 2) r = min(r, d[x]);
    return r;
  }
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int n, m;
  cin >> n >> m;

  vpii ie(m);
  vll len(m), ext(m);
  vint p(n + 1);
  iota(all(p), 0);
  function<int(int)> f = [&](int x){ return p[x] = (x == p[x] ? x : f(p[x])); };
  for(int i = 0; i < m; i++) {
    cin >> ie[i].x >> ie[i].y >> len[i];
    if(len[i] == 0) p[f(ie[i].y)] = f(ie[i].x);
  }  
  for(int i = m - 2; i >= 0; i--) ext[i] = max(ext[i + 1], len[i + 1]);

  vector<vpii> e(n + 1);
  for(int i = 0; i < m; i++){
    int x = f(ie[i].x), y = f(ie[i].y);
    if(x == y) continue;
    e[x].emplace_back(y, i);
    e[y].emplace_back(x, i);
  }

  vll ds(n + 1), de(n + 1);
  auto fnd = [&](int st, vll &d) {
    priority_queue<pli, vector<pli>, greater<pli>> pq;
    fill(all(d), INF);
    d[st] = 0;
    pq.emplace(0LL, st);
    while(!pq.empty()) {
      pli c = pq.top();
      pq.pop();
      if(c.x != d[c.y]) continue;
      for(pii &p : e[c.y]) {
        if(d[p.x] > c.x + len[p.y]) {
          d[p.x] = c.x + len[p.y];
          pq.emplace(d[p.x], p.x);
        }
      }
    }
  };
  fnd(f(1), ds);
  fnd(f(n), de);

  vint path(n + 1);
  for(int x = f(1), c = 1; ; c++) {
    path[x] = c;
    if(x == f(n)) break;
    for(pii &p : e[x]) {
      if(ds[p.x] == ds[x] + len[p.y] && de[p.x] + len[p.y] == de[x]) {
        x = p.x;
        Seg::u(c, c, ds[f(n)] + ext[p.y]);
        break;
      }
    }
  }

  vint ms(n + 1), me(n + 1);
  function<int(int, int, vint&, const vll&)> g =
  [&](int x, int mode, vint &mem, const vll &d) {
    if(path[x]) return path[x];
    if(mem[x]) return mem[x];
    mem[x] = (mode == 0 ? n + 1 : -1);
    for(pii &p : e[x]) if(d[x] == d[p.x] + len[p.y]) {
      mem[x] = (
        mode == 0
        ? min(mem[x], g(p.x, mode, mem, d))
        : max(mem[x], g(p.x, mode, mem, d))
      );
    }
    return mem[x];
  };

  for(int i = 1; i <= n; i++) {
    for(pii &p : e[i]) {
      if(path[i] && path[p.x]) continue;
      int A = g(i, 0, ms, ds), B = g(p.x, 1, me, de);
      Seg::u(A, B, ds[i] + de[p.x] + len[p.y]);
      A = g(p.x, 0, ms, ds), B = g(i, 1, me, de);
      Seg::u(A, B, ds[p.x] + de[i] + len[p.y]);
    }
  }

  ll ans = 0;
  for(int i = 1; ; i++) {
    ll t = Seg::g(i);
    if(t == INF) break;
    ans = max(ans, t);
  }
  cout << ans << '\n';

  return 0;
}

Compilation message

Aesthetic.cpp: In function 'void Seg::u(int, int, ll)':
Aesthetic.cpp:31:20: warning: operation on 's' may be undefined [-Wsequence-point]
   31 |       if(s & 1) d[s++] = min(d[s], v);
      |                   ~^~
Aesthetic.cpp:32:21: warning: operation on 'e' may be undefined [-Wsequence-point]
   32 |       if(~e & 1) d[e--] = min(d[e], v);
      |                    ~^~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8576 KB Output is correct
2 Incorrect 6 ms 8576 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8576 KB Output is correct
2 Incorrect 6 ms 8576 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 863 ms 45704 KB Output is correct
2 Correct 852 ms 49656 KB Output is correct
3 Correct 808 ms 49016 KB Output is correct
4 Correct 792 ms 49016 KB Output is correct
5 Incorrect 786 ms 49272 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 827 ms 46200 KB Output is correct
2 Correct 839 ms 49528 KB Output is correct
3 Incorrect 809 ms 49728 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 746 ms 40040 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 746 ms 40040 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8576 KB Output is correct
2 Incorrect 6 ms 8576 KB Output isn't correct
3 Halted 0 ms 0 KB -