oj.uz

Submission #284265

# Submission time Handle Problem Language Result Execution time Memory
284265 2020-08-27T06:07:19 Z 김동현(#5767) Aesthetic (NOI20_aesthetic) C++17
35 / 100
 881 ms 44280 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(ds[i] + de[p.x] + len[p.y] == ds[f(n)]) continue;
      if(ds[p.x] + de[i] + len[p.y] == ds[f(n)]) continue;
      int A = g(i, 0, ms, ds), B = g(p.x, 1, me, de);
      Seg::u(A, B - 1, 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 - 1, 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
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8704 KB Output is correct
2 Correct 5 ms 8576 KB Output is correct
3 Correct 5 ms 8576 KB Output is correct
4 Correct 5 ms 8576 KB Output is correct
5 Correct 5 ms 8576 KB Output is correct
6 Correct 5 ms 8576 KB Output is correct
7 Correct 5 ms 8576 KB Output is correct
8 Correct 6 ms 8576 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8704 KB Output is correct
2 Correct 5 ms 8576 KB Output is correct
3 Correct 5 ms 8576 KB Output is correct
4 Correct 5 ms 8576 KB Output is correct
5 Correct 5 ms 8576 KB Output is correct
6 Correct 5 ms 8576 KB Output is correct
7 Correct 5 ms 8576 KB Output is correct
8 Correct 6 ms 8576 KB Output is correct
9 Correct 7 ms 8832 KB Output is correct
10 Correct 7 ms 8760 KB Output is correct
11 Correct 7 ms 8832 KB Output is correct
12 Correct 7 ms 8832 KB Output is correct
13 Correct 6 ms 8704 KB Output is correct
14 Correct 7 ms 8704 KB Output is correct
15 Correct 8 ms 8704 KB Output is correct
16 Correct 7 ms 8704 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 822 ms 43948 KB Output is correct
2 Correct 810 ms 43640 KB Output is correct
3 Correct 838 ms 43128 KB Output is correct
4 Correct 839 ms 43252 KB Output is correct
5 Correct 827 ms 43404 KB Output is correct
6 Correct 823 ms 43768 KB Output is correct
7 Correct 837 ms 43768 KB Output is correct
8 Correct 881 ms 43856 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 829 ms 44280 KB Output is correct
2 Correct 844 ms 43512 KB Output is correct
3 Correct 814 ms 43612 KB Output is correct
4 Correct 831 ms 43924 KB Output is correct
5 Correct 838 ms 43128 KB Output is correct
6 Correct 830 ms 43512 KB Output is correct
7 Correct 848 ms 43256 KB Output is correct
8 Correct 844 ms 43640 KB Output is correct

Subtask #5
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 784 ms 37992 KB Output is correct
2 Correct 264 ms 39160 KB Output is correct
3 Incorrect 272 ms 30252 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 784 ms 37992 KB Output is correct
2 Correct 264 ms 39160 KB Output is correct
3 Incorrect 272 ms 30252 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8704 KB Output is correct
2 Correct 5 ms 8576 KB Output is correct
3 Correct 5 ms 8576 KB Output is correct
4 Correct 5 ms 8576 KB Output is correct
5 Correct 5 ms 8576 KB Output is correct
6 Correct 5 ms 8576 KB Output is correct
7 Correct 5 ms 8576 KB Output is correct
8 Correct 6 ms 8576 KB Output is correct
9 Correct 7 ms 8832 KB Output is correct
10 Correct 7 ms 8760 KB Output is correct
11 Correct 7 ms 8832 KB Output is correct
12 Correct 7 ms 8832 KB Output is correct
13 Correct 6 ms 8704 KB Output is correct
14 Correct 7 ms 8704 KB Output is correct
15 Correct 8 ms 8704 KB Output is correct
16 Correct 7 ms 8704 KB Output is correct
17 Correct 822 ms 43948 KB Output is correct
18 Correct 810 ms 43640 KB Output is correct
19 Correct 838 ms 43128 KB Output is correct
20 Correct 839 ms 43252 KB Output is correct
21 Correct 827 ms 43404 KB Output is correct
22 Correct 823 ms 43768 KB Output is correct
23 Correct 837 ms 43768 KB Output is correct
24 Correct 881 ms 43856 KB Output is correct
25 Correct 829 ms 44280 KB Output is correct
26 Correct 844 ms 43512 KB Output is correct
27 Correct 814 ms 43612 KB Output is correct
28 Correct 831 ms 43924 KB Output is correct
29 Correct 838 ms 43128 KB Output is correct
30 Correct 830 ms 43512 KB Output is correct
31 Correct 848 ms 43256 KB Output is correct
32 Correct 844 ms 43640 KB Output is correct
33 Correct 784 ms 37992 KB Output is correct
34 Correct 264 ms 39160 KB Output is correct
35 Incorrect 272 ms 30252 KB Output isn't correct
36 Halted 0 ms 0 KB -