Submission #4021076


Source Code Expand

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vector<int>> vvi;
typedef vector<vector<ll>> vvl;

struct N {
  int i;
  ll val;
  bool a;
};
bool operator<(const N &l, const N &r) { return l.val < r.val; }

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int n;
  cin >> n;
  vector<N> v(n * 2);
  vll a(n), b(n);
  for (int i = 0; i < n; i++) {
    cin >> v[i * 2].val >> v[i * 2 + 1].val;
    a[i] = v[i * 2].val;
    b[i] = v[i * 2 + 1].val;
    v[i * 2].i = i;
    v[i * 2 + 1].i = i;
    v[i * 2].a = true;
    v[i * 2 + 1].a = false;
  }
  ll ans = 0;
  ll sa = 0, sb = 0;
  for (int i = 0; i < n; i++) {
    sa += a[i];
    sb += b[i];
  }
  ans = min(sa, sb);
  vi count(n);
  sort(v.begin(), v.end());
  for (int i = 0; i < n; i++)
    count[v[i].i]++;
  bool ok = false;
  for (int i = 0; i < n; i++) {
    if (count[i] == 2)
      ok = true;
  }
  if (ok) {
    ll sum = 0;
    for (int i = 0; i < n; i++)
      sum += v[i].val;
    ans = min(ans, sum);
  } else {
    ll sum = 0;
    for (int i = 0; i < n; i++)
      sum += v[i].val;
    for (int i = 0; i < n; i++) {
      ll sc = sum;
      if (count[i] > 0) {
        sc -= min(a[i], b[i]);
        int k = 0;
        while (true) {
          if (v[n + k].i != i) {
            sc += v[n + k].val;
            break;
          }
          k++;
        }
        ans = min(ans, sc);
      }
    }
  }
  cout << ans << endl;
  return 0;
}

Submission Info

Submission Time
Task C - Min Cost Cycle
User ninja7
Language C++14 (GCC 5.4.1)
Score 700
Code Size 1578 Byte
Status AC
Exec Time 39 ms
Memory 6912 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 700 / 700
Status
AC × 3
AC × 31
Set Name Test Cases
Sample sample-01.txt, sample-02.txt, sample-03.txt
All sample-01.txt, sample-02.txt, sample-03.txt, sample-01.txt, sample-02.txt, sample-03.txt, subtask01-01.txt, subtask01-02.txt, subtask01-03.txt, subtask01-04.txt, subtask01-05.txt, subtask01-06.txt, subtask01-07.txt, subtask01-08.txt, subtask01-09.txt, subtask01-10.txt, subtask01-11.txt, subtask01-12.txt, subtask01-13.txt, subtask01-14.txt, subtask01-15.txt, subtask01-16.txt, subtask01-17.txt, subtask01-18.txt, subtask01-19.txt, subtask01-20.txt, subtask01-21.txt, subtask01-22.txt, subtask01-23.txt, subtask01-24.txt, subtask01-25.txt
Case Name Status Exec Time Memory
sample-01.txt AC 1 ms 256 KB
sample-02.txt AC 1 ms 256 KB
sample-03.txt AC 1 ms 256 KB
subtask01-01.txt AC 1 ms 256 KB
subtask01-02.txt AC 27 ms 4864 KB
subtask01-03.txt AC 38 ms 6656 KB
subtask01-04.txt AC 2 ms 256 KB
subtask01-05.txt AC 25 ms 4480 KB
subtask01-06.txt AC 27 ms 4736 KB
subtask01-07.txt AC 37 ms 6528 KB
subtask01-08.txt AC 34 ms 6144 KB
subtask01-09.txt AC 24 ms 4352 KB
subtask01-10.txt AC 26 ms 4608 KB
subtask01-11.txt AC 32 ms 5760 KB
subtask01-12.txt AC 34 ms 6016 KB
subtask01-13.txt AC 20 ms 3584 KB
subtask01-14.txt AC 39 ms 6912 KB
subtask01-15.txt AC 38 ms 6912 KB
subtask01-16.txt AC 39 ms 6912 KB
subtask01-17.txt AC 39 ms 6912 KB
subtask01-18.txt AC 39 ms 6912 KB
subtask01-19.txt AC 39 ms 6912 KB
subtask01-20.txt AC 38 ms 6912 KB
subtask01-21.txt AC 39 ms 6912 KB
subtask01-22.txt AC 39 ms 6912 KB
subtask01-23.txt AC 39 ms 6912 KB
subtask01-24.txt AC 38 ms 6912 KB
subtask01-25.txt AC 39 ms 6912 KB