oj.uz

Submission #284262

# Submission time Handle Problem Language Result Execution time Memory
284262 2020-08-27T06:01:52 Z 김동현(#5767) Aesthetic (NOI20_aesthetic) C++17
51 / 100
 842 ms 51448 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 - 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 8576 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 7 ms 8576 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8576 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 7 ms 8576 KB Output is correct
9 Correct 7 ms 8832 KB Output is correct
10 Correct 7 ms 8832 KB Output is correct
11 Correct 7 ms 8832 KB Output is correct
12 Correct 7 ms 8832 KB Output is correct
13 Correct 7 ms 8704 KB Output is correct
14 Correct 7 ms 8704 KB Output is correct
15 Correct 7 ms 8704 KB Output is correct
16 Correct 8 ms 8704 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 804 ms 43636 KB Output is correct
2 Correct 828 ms 43576 KB Output is correct
3 Correct 797 ms 43236 KB Output is correct
4 Correct 809 ms 43132 KB Output is correct
5 Correct 782 ms 43480 KB Output is correct
6 Correct 813 ms 50348 KB Output is correct
7 Correct 817 ms 50284 KB Output is correct
8 Correct 834 ms 50336 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 823 ms 44032 KB Output is correct
2 Correct 833 ms 43732 KB Output is correct
3 Correct 799 ms 43644 KB Output is correct
4 Correct 800 ms 50424 KB Output is correct
5 Correct 782 ms 49388 KB Output is correct
6 Correct 789 ms 49784 KB Output is correct
7 Correct 814 ms 49656 KB Output is correct
8 Correct 842 ms 49844 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 778 ms 37864 KB Output is correct
2 Correct 296 ms 43228 KB Output is correct
3 Correct 381 ms 33912 KB Output is correct
4 Correct 392 ms 33912 KB Output is correct
5 Correct 377 ms 33912 KB Output is correct
6 Correct 382 ms 33976 KB Output is correct
7 Correct 371 ms 33920 KB Output is correct
8 Correct 365 ms 33912 KB Output is correct
9 Correct 377 ms 33988 KB Output is correct
10 Correct 377 ms 34124 KB Output is correct
11 Correct 345 ms 33912 KB Output is correct
12 Correct 738 ms 41476 KB Output is correct
13 Correct 327 ms 34056 KB Output is correct
14 Correct 220 ms 51448 KB Output is correct
15 Correct 219 ms 51448 KB Output is correct
16 Correct 708 ms 41164 KB Output is correct
17 Correct 720 ms 40316 KB Output is correct
18 Correct 763 ms 40936 KB Output is correct
19 Correct 276 ms 43352 KB Output is correct
20 Correct 262 ms 43384 KB Output is correct
21 Correct 254 ms 43256 KB Output is correct
22 Correct 254 ms 43256 KB Output is correct

Subtask #6
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 778 ms 37864 KB Output is correct
2 Correct 296 ms 43228 KB Output is correct
3 Correct 381 ms 33912 KB Output is correct
4 Correct 392 ms 33912 KB Output is correct
5 Correct 377 ms 33912 KB Output is correct
6 Correct 382 ms 33976 KB Output is correct
7 Correct 371 ms 33920 KB Output is correct
8 Correct 365 ms 33912 KB Output is correct
9 Correct 377 ms 33988 KB Output is correct
10 Correct 377 ms 34124 KB Output is correct
11 Correct 345 ms 33912 KB Output is correct
12 Correct 738 ms 41476 KB Output is correct
13 Correct 327 ms 34056 KB Output is correct
14 Correct 220 ms 51448 KB Output is correct
15 Correct 219 ms 51448 KB Output is correct
16 Correct 708 ms 41164 KB Output is correct
17 Correct 720 ms 40316 KB Output is correct
18 Correct 763 ms 40936 KB Output is correct
19 Correct 276 ms 43352 KB Output is correct
20 Correct 262 ms 43384 KB Output is correct
21 Correct 254 ms 43256 KB Output is correct
22 Correct 254 ms 43256 KB Output is correct
23 Correct 681 ms 40420 KB Output is correct
24 Correct 262 ms 42488 KB Output is correct
25 Correct 344 ms 34044 KB Output is correct
26 Correct 357 ms 33996 KB Output is correct
27 Correct 358 ms 33912 KB Output is correct
28 Correct 353 ms 33912 KB Output is correct
29 Correct 338 ms 34040 KB Output is correct
30 Correct 334 ms 34040 KB Output is correct
31 Correct 359 ms 34296 KB Output is correct
32 Correct 337 ms 34040 KB Output is correct
33 Correct 357 ms 34168 KB Output is correct
34 Correct 690 ms 40048 KB Output is correct
35 Correct 355 ms 34168 KB Output is correct
36 Incorrect 99 ms 27512 KB Output isn't correct
37 Halted 0 ms 0 KB -

Subtask #7
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8576 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 7 ms 8576 KB Output is correct
9 Correct 7 ms 8832 KB Output is correct
10 Correct 7 ms 8832 KB Output is correct
11 Correct 7 ms 8832 KB Output is correct
12 Correct 7 ms 8832 KB Output is correct
13 Correct 7 ms 8704 KB Output is correct
14 Correct 7 ms 8704 KB Output is correct
15 Correct 7 ms 8704 KB Output is correct
16 Correct 8 ms 8704 KB Output is correct
17 Correct 804 ms 43636 KB Output is correct
18 Correct 828 ms 43576 KB Output is correct
19 Correct 797 ms 43236 KB Output is correct
20 Correct 809 ms 43132 KB Output is correct
21 Correct 782 ms 43480 KB Output is correct
22 Correct 813 ms 50348 KB Output is correct
23 Correct 817 ms 50284 KB Output is correct
24 Correct 834 ms 50336 KB Output is correct
25 Correct 823 ms 44032 KB Output is correct
26 Correct 833 ms 43732 KB Output is correct
27 Correct 799 ms 43644 KB Output is correct
28 Correct 800 ms 50424 KB Output is correct
29 Correct 782 ms 49388 KB Output is correct
30 Correct 789 ms 49784 KB Output is correct
31 Correct 814 ms 49656 KB Output is correct
32 Correct 842 ms 49844 KB Output is correct
33 Correct 778 ms 37864 KB Output is correct
34 Correct 296 ms 43228 KB Output is correct
35 Correct 381 ms 33912 KB Output is correct
36 Correct 392 ms 33912 KB Output is correct
37 Correct 377 ms 33912 KB Output is correct
38 Correct 382 ms 33976 KB Output is correct
39 Correct 371 ms 33920 KB Output is correct
40 Correct 365 ms 33912 KB Output is correct
41 Correct 377 ms 33988 KB Output is correct
42 Correct 377 ms 34124 KB Output is correct
43 Correct 345 ms 33912 KB Output is correct
44 Correct 738 ms 41476 KB Output is correct
45 Correct 327 ms 34056 KB Output is correct
46 Correct 220 ms 51448 KB Output is correct
47 Correct 219 ms 51448 KB Output is correct
48 Correct 708 ms 41164 KB Output is correct
49 Correct 720 ms 40316 KB Output is correct
50 Correct 763 ms 40936 KB Output is correct
51 Correct 276 ms 43352 KB Output is correct
52 Correct 262 ms 43384 KB Output is correct
53 Correct 254 ms 43256 KB Output is correct
54 Correct 254 ms 43256 KB Output is correct
55 Correct 681 ms 40420 KB Output is correct
56 Correct 262 ms 42488 KB Output is correct
57 Correct 344 ms 34044 KB Output is correct
58 Correct 357 ms 33996 KB Output is correct
59 Correct 358 ms 33912 KB Output is correct
60 Correct 353 ms 33912 KB Output is correct
61 Correct 338 ms 34040 KB Output is correct
62 Correct 334 ms 34040 KB Output is correct
63 Correct 359 ms 34296 KB Output is correct
64 Correct 337 ms 34040 KB Output is correct
65 Correct 357 ms 34168 KB Output is correct
66 Correct 690 ms 40048 KB Output is correct
67 Correct 355 ms 34168 KB Output is correct
68 Incorrect 99 ms 27512 KB Output isn't correct
69 Halted 0 ms 0 KB -