QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#243879#7762. 数据库hos_lyric#40 134ms4284kbC++146.3kb2023-11-08 18:52:132024-07-04 02:23:22

Judging History

你现在查看的是最新测评结果

  • [2024-07-04 02:23:22]
  • 评测
  • 测评结果:40
  • 用时:134ms
  • 内存:4284kb
  • [2023-11-08 18:52:13]
  • 提交

answer

#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;

using Int = long long;

template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }
#define COLOR(s) ("\x1b[" s "m")


// Minimum cost flow by successive shortest paths.
// Assumes that there exists no negative-cost cycle.
// TODO: Check the range of intermediate values.
template <class Flow, class Cost> struct MinCostFlow {
  // Watch out when using types other than int and long long.
  static constexpr Flow FLOW_EPS = 1e-10L;
  static constexpr Flow FLOW_INF = std::numeric_limits<Flow>::max();
  static constexpr Cost COST_EPS = 1e-10L;
  static constexpr Cost COST_INF = std::numeric_limits<Cost>::max();

  int n, m;
  vector<int> ptr, nxt, zu;
  vector<Flow> capa;
  vector<Cost> cost;

  explicit MinCostFlow(int n_) : n(n_), m(0), ptr(n_, -1) {}
  void ae(int u, int v, Flow w, Cost c) {
    assert(0 <= u); assert(u < n);
    assert(0 <= v); assert(v < n);
    assert(0 <= w);
    nxt.push_back(ptr[u]); zu.push_back(v); capa.push_back(w); cost.push_back( c); ptr[u] = m++;
    nxt.push_back(ptr[v]); zu.push_back(u); capa.push_back(0); cost.push_back(-c); ptr[v] = m++;
  }

  vector<Cost> pot, dist;
  vector<bool> vis;
  vector<int> pari;

  // cost slopes[j] per flow when flows[j] <= flow <= flows[j + 1]
  vector<Flow> flows;
  vector<Cost> slopes;

  // Finds a shortest path from s to t in the residual graph.
  // O((n + m) log m) time.
  //   Assumes that the members above are set.
  //   The distance to a vertex might not be determined if it is >= dist[t].
  //   You can pass t = -1 to find a shortest path to each vertex.
  void shortest(int s, int t) {
    using Entry = pair<Cost, int>;
    priority_queue<Entry, vector<Entry>, std::greater<Entry>> que;
    for (int u = 0; u < n; ++u) { dist[u] = COST_INF; vis[u] = false; }
    for (que.emplace(dist[s] = 0, s); !que.empty(); ) {
      const Cost c = que.top().first;
      const int u = que.top().second;
      que.pop();
      if (vis[u]) continue;
      vis[u] = true;
      if (u == t) return;
      for (int i = ptr[u]; ~i; i = nxt[i]) if (capa[i] > FLOW_EPS) {
        const int v = zu[i];
        if (!vis[v]) {
          const Cost cc = c + cost[i] + pot[u] - pot[v];
          if (dist[v] > cc) { que.emplace(dist[v] = cc, v); pari[v] = i; }
        }
      }
    }
  }

  // Finds a minimum cost flow from s to t of amount min{(max flow), limFlow}.
  //   Bellman-Ford takes O(n m) time, or O(m) time if there is no negative-cost
  //   edge, or cannot stop if there exists a negative-cost cycle.
  //   min{(max flow), limFlow} shortest paths if Flow is an integral type.
  pair<Flow, Cost> run(int s, int t, Flow limFlow = FLOW_INF) {
    assert(0 <= s); assert(s < n);
    assert(0 <= t); assert(t < n);
    assert(s != t);
    assert(0 <= limFlow);
    pot.assign(n, 0);
    for (; ; ) {
      bool upd = false;
      for (int i = 0; i < m; ++i) if (capa[i] > FLOW_EPS) {
        const int u = zu[i ^ 1], v = zu[i];
        const Cost cc = pot[u] + cost[i];
        if (pot[v] > cc + COST_EPS) { pot[v] = cc; upd = true; }
      }
      if (!upd) break;
    }
    dist.resize(n);
    vis.resize(n);
    pari.resize(n);
    Flow totalFlow = 0;
    Cost totalCost = 0;
    flows.clear(); flows.push_back(0);
    slopes.clear();
    for (; totalFlow < limFlow; ) {
      shortest(s, t);
      if (!vis[t]) break;
      for (int u = 0; u < n; ++u) pot[u] += min(dist[u], dist[t]);
      Flow f = limFlow - totalFlow;
      for (int v = t; v != s; ) {
        const int i = pari[v]; if (f > capa[i]) { f = capa[i]; } v = zu[i ^ 1];
      }
      for (int v = t; v != s; ) {
        const int i = pari[v]; capa[i] -= f; capa[i ^ 1] += f; v = zu[i ^ 1];
      }
      totalFlow += f;
      totalCost += f * (pot[t] - pot[s]);
      flows.push_back(totalFlow);
      slopes.push_back(pot[t] - pot[s]);
    }
    return make_pair(totalFlow, totalCost);
  }
};

////////////////////////////////////////////////////////////////////////////////


int N, M, Q;
vector<int> W;
vector<int> K;

int main() {
  for (; ~scanf("%d%d%d", &N, &M, &Q); ) {
    W.resize(N);
    for (int k = 0; k < N; ++k) {
      scanf("%d", &W[k]);
    }
    K.resize(Q);
    for (int q = 0; q < Q; ++q) {
      scanf("%d", &K[q]);
      --K[q];
    }
    
    MinCostFlow<int, int> mcf(2 + (Q + 1) + Q * 2);
    auto point = [&](int q) -> int { return 2 + q; };
    auto in = [&](int q) -> int { return 2 + (Q + 1) + q * 2; };
    auto out = [&](int q) -> int { return 2 + (Q + 1) + q * 2 + 1; };
    mcf.ae(0, point(0), M, 0);
    mcf.ae(point(Q), 1, M, 0);
    for (int q = 0; q < Q; ++q) {
      mcf.ae(point(q), point(q + 1), M, 0);
    }
    for (int q = 0; q < Q; ++q) {
      const int u = in(q), v = out(q);
      mcf.ae(point(q), u, 1, W[K[q]]);
      mcf.ae(v, point(q + 1), 1, 0);
      // u -> v, at least 1
      mcf.ae(0, v, 1, 0);
      mcf.ae(u, 1, 1, 0);
    }
    vector<int> app(N, -1);
    for (int qR = 0; qR < Q; ++qR) {
      const int qL = app[K[qR]];
      if (~qL) {
        mcf.ae(out(qL), in(qR), 1, 0);
      }
      app[K[qR]] = qR;
    }
    
    const auto res = mcf.run(0, 1, M + Q);
    printf("%d\n", res.second);
  }
  return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Time Limit Exceeded

Test #1:

score: 0
Time Limit Exceeded

input:

10 3 5000
23077 34848 88221 8067 83132 62621 41320 69146 32971 27594
2 7 5 3 9 6 1 9 4 8 1 8 8 3 6 9 1 7 5 5 6 8 1 3 10 6 8 7 10 2 1 2 6 7 5 5 9 5 7 10 10 6 6 7 2 4 3 1 10 10 5 1 1 6 1 2 8 9 2 5 10 1 10 7 5 5 10 5 2 5 6 10 9 5 6 3 5 3 6 5 7 4 1 5 8 1 1 9 7 1 1 2 1 8 6 2 9 8 4 2 5 4 5 2 10 4 3 6 9 7 ...

output:


result:


Subtask #2:

score: 0
Time Limit Exceeded

Test #4:

score: 0
Time Limit Exceeded

input:

10 2 5000
65644 5214 85000 40719 98071 56616 35404 16019 96748 89032
5 9 6 1 3 6 8 10 2 9 1 10 5 9 9 9 2 7 7 7 7 10 5 1 3 10 4 2 5 5 2 8 3 2 1 3 3 6 2 4 5 5 2 5 2 3 4 2 10 1 4 6 10 9 6 4 9 10 5 3 9 7 7 2 1 9 5 8 8 4 8 8 4 5 6 1 3 4 8 10 4 3 6 6 9 2 5 2 8 5 10 4 7 10 3 9 3 2 9 3 10 7 1 3 9 9 3 5 1 3 ...

output:


result:


Subtask #3:

score: 20
Accepted

Test #7:

score: 20
Accepted
time: 15ms
memory: 3976kb

input:

5000 15 400
34145 93322 29976 7963 53362 50640 10859 94528 13329 49980 18826 50286 60155 79748 73253 18329 5216 83079 48220 98825 46592 76855 14037 19859 80960 4461 377 70496 28092 99806 5355 27013 92051 95231 65553 32365 3862 89764 86063 93033 12754 68996 38965 52942 69948 34370 3023 52079 16066 57...

output:

19341503

result:

ok single line: '19341503'

Test #8:

score: 0
Accepted
time: 19ms
memory: 3832kb

input:

5000 15 400
68511 70579 96844 20943 72871 28340 68790 60294 76760 12623 80406 65418 37942 2849 76307 28818 18555 42151 94506 78241 15350 11345 76323 21860 22703 31009 24763 71007 60858 53746 28720 5027 72512 39122 55299 41675 88475 94331 78711 3464 80345 69031 98746 14792 97862 97255 5853 92742 9096...

output:

19515326

result:

ok single line: '19515326'

Test #9:

score: 0
Accepted
time: 20ms
memory: 4244kb

input:

5000 15 400
18305 15347 86331 37503 78391 3378 82447 51150 49032 2422 47659 20516 18666 16520 27948 17865 45842 66799 35584 75288 46358 21654 30233 25291 44810 27579 93986 15174 56012 48286 66826 93615 77979 40669 17262 77857 82134 50752 19642 77961 55856 68600 60598 33035 94214 17392 16736 21460 58...

output:

18253485

result:

ok single line: '18253485'

Subtask #4:

score: 20
Accepted

Test #10:

score: 20
Accepted
time: 54ms
memory: 3992kb

input:

10 5 1000
86764 81108 88408 93029 87155 18790 28170 29349 81866 77109
8 7 10 7 2 7 1 8 4 10 9 10 4 1 7 1 9 9 1 6 6 1 9 6 7 1 8 10 1 7 9 1 1 9 7 10 8 5 5 1 2 3 10 6 2 6 2 6 1 2 7 8 5 6 10 2 9 8 2 6 8 5 10 8 1 10 4 6 5 6 3 8 1 3 5 2 2 7 2 4 5 5 8 2 4 1 3 6 8 2 2 3 1 8 1 5 8 6 9 7 7 3 7 9 8 9 9 7 5 3 6...

output:

15248002

result:

ok single line: '15248002'

Test #11:

score: 0
Accepted
time: 50ms
memory: 4060kb

input:

10 10 1000
57793 91210 18011 676 38391 78527 56352 69343 95947 5616
5 8 4 5 10 6 1 7 3 10 2 7 1 9 5 3 5 8 3 8 7 10 2 10 6 1 4 3 6 10 6 3 8 4 3 9 1 6 10 3 10 1 6 2 9 9 3 5 8 8 3 9 1 5 9 9 3 3 7 9 2 4 1 9 8 3 1 2 8 9 10 9 4 3 10 5 4 4 8 6 6 9 3 3 2 3 7 2 3 3 10 4 5 5 6 4 2 5 10 1 2 6 9 8 7 9 4 8 2 1 2...

output:

511866

result:

ok single line: '511866'

Test #12:

score: 0
Accepted
time: 57ms
memory: 3956kb

input:

10 15 1000
19536 14188 62086 25660 67447 48774 97871 17167 8671 85361
3 5 2 6 4 6 10 5 7 6 10 8 1 9 5 7 5 5 2 10 7 10 8 6 3 4 2 2 8 9 6 10 9 10 10 9 6 1 7 2 1 10 8 10 3 9 1 8 10 4 6 9 9 8 1 5 2 10 9 1 3 6 5 6 2 5 3 9 6 5 6 10 5 6 10 4 6 6 8 8 9 5 2 10 1 10 7 4 2 6 10 5 6 2 3 1 3 9 8 3 9 7 7 7 2 6 7 ...

output:

446761

result:

ok single line: '446761'

Test #13:

score: 0
Accepted
time: 81ms
memory: 3980kb

input:

100 5 1000
95646 33117 46458 52069 38647 38645 60235 93897 41039 35835 49580 92470 5371 6812 38049 9178 50163 92322 9735 27037 58888 49095 68473 5472 1644 94513 50597 10246 96329 51334 1986 79907 89526 10771 29923 55249 59048 91934 46853 79352 85644 57708 57300 20536 70782 61882 58712 97314 45686 55...

output:

36018137

result:

ok single line: '36018137'

Test #14:

score: 0
Accepted
time: 82ms
memory: 3960kb

input:

100 10 1000
36326 35981 96633 82565 65884 23199 50344 49682 96971 42033 2351 31928 50056 73426 36217 89994 30603 27971 17757 19901 99501 35915 27895 26451 91714 36134 94294 19114 22490 97680 48272 80639 24603 93000 28420 7595 7314 52546 12258 58666 88422 29237 69223 41046 13515 72493 26486 34554 239...

output:

30951978

result:

ok single line: '30951978'

Test #15:

score: 0
Accepted
time: 80ms
memory: 3984kb

input:

100 15 1000
60259 28844 6884 35222 45974 11055 13021 13966 14853 85552 12283 29760 50104 63448 84364 1684 99886 31837 61724 84415 28292 81814 31562 60077 93784 1729 1602 56374 19276 89781 13359 78765 97380 34118 39756 12254 61197 53500 95962 61254 16553 24467 58101 53482 65199 75076 67326 92045 306 ...

output:

26014456

result:

ok single line: '26014456'

Test #16:

score: 0
Accepted
time: 132ms
memory: 3996kb

input:

1000 5 1000
84587 68464 19119 74315 48972 23581 58263 43666 21662 5458 47594 18617 52236 24283 45998 66734 8501 94413 31981 77247 50069 95649 21536 8055 62698 98164 14074 22987 14525 12396 7681 17830 97091 88885 86419 1067 92977 54999 33673 9550 67710 98546 82017 17583 667 36168 61540 74015 42193 48...

output:

45688268

result:

ok single line: '45688268'

Test #17:

score: 0
Accepted
time: 128ms
memory: 4000kb

input:

1000 10 1000
24129 67704 68122 93372 94874 19813 14041 20830 97805 57074 99877 64455 80825 93755 98668 89675 35445 42895 74964 71326 43884 8123 1767 83698 2892 77832 21668 85066 17440 49874 77903 22427 45669 41174 40029 27379 61235 13563 4313 90065 99573 45555 19683 39486 76606 30438 34528 180 83016...

output:

44994110

result:

ok single line: '44994110'

Test #18:

score: 0
Accepted
time: 134ms
memory: 4284kb

input:

1000 15 1000
59991 63683 65484 87716 79869 15955 13746 80474 77381 51499 17028 13036 18275 82716 12845 66038 16310 66787 28778 73107 90796 63216 85094 24799 99979 96956 35994 21067 81494 75695 91088 34745 82075 27522 293 67267 51879 50823 80429 54323 21127 60258 40463 26950 69326 7049 39530 62048 23...

output:

39885004

result:

ok single line: '39885004'

Subtask #5:

score: 0
Skipped

Dependency #1:

0%