Submission #4024472


Source Code Expand

#include <bits/stdc++.h>
using namespace std;
using ll = int64_t;
using P = pair<ll, ll>;
const ll INF = 5e15;
const ll MOD = 1e9 + 7;

ll N;

struct Cost {
    ll cost;
    ll idx;
    bool A;
    Cost(ll c, ll i, bool A) : cost(c), idx(i), A(A) {}
};

bool valid(const set<ll> &SA, const set<ll> &SB){
    if(SA.empty() || SB.empty()) return true;
    set<ll> tmp;
    for(ll e : SA) tmp.insert(e);
    for(ll e : SB) tmp.insert(e);
    return tmp.size() != N;
}

int main(){
    cin >> N;
    vector<Cost> v;
    for(ll i = 0; i < N; i++){
        ll a, b;
        cin >> a >> b;
        v.push_back(Cost(a, i, true));
        v.push_back(Cost(b, i, false));
    }
    sort(v.begin(), v.end(), [](const auto &a, const auto &b){ return a.cost < b.cost; });
    set<ll> SA, SB;
    ll ans = 0;
    for(ll i = 0; i < N; i++){
        (v[i].A ? SA : SB).insert(v[i].idx);
        ans += v[i].cost;
    }
    if(!valid(SA, SB)){
        (v[N - 1].A ? SA : SB).erase(v[N - 1].idx);
        (v[N].A ? SA : SB).insert(v[N].idx);
        if(valid(SA, SB)){
            ans -= v[N - 1].cost;
            ans += v[N].cost;
        }else{
            ll v1 = v[N - 1].cost + v[N].cost - v[0].cost;
            ll v2 = v[N + 1].cost;
            ans += min(v1, v2);
            }
    }
    cout << ans << endl;
    return 0;
}

Submission Info

Submission Time
Task C - Min Cost Cycle
User kcvlex
Language C++14 (GCC 5.4.1)
Score 0
Code Size 1372 Byte
Status WA
Exec Time 167 ms
Memory 15468 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 700
Status
AC × 3
AC × 25
WA × 6
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 99 ms 10604 KB
subtask01-03.txt AC 122 ms 10476 KB
subtask01-04.txt AC 2 ms 384 KB
subtask01-05.txt WA 99 ms 9200 KB
subtask01-06.txt AC 96 ms 9324 KB
subtask01-07.txt AC 119 ms 10604 KB
subtask01-08.txt AC 141 ms 13548 KB
subtask01-09.txt WA 95 ms 9072 KB
subtask01-10.txt AC 92 ms 8688 KB
subtask01-11.txt AC 105 ms 9836 KB
subtask01-12.txt AC 136 ms 13804 KB
subtask01-13.txt WA 75 ms 7664 KB
subtask01-14.txt AC 146 ms 13164 KB
subtask01-15.txt AC 127 ms 10348 KB
subtask01-16.txt AC 162 ms 14828 KB
subtask01-17.txt WA 159 ms 14316 KB
subtask01-18.txt AC 144 ms 13164 KB
subtask01-19.txt AC 126 ms 10092 KB
subtask01-20.txt AC 159 ms 15084 KB
subtask01-21.txt WA 159 ms 14444 KB
subtask01-22.txt AC 146 ms 13164 KB
subtask01-23.txt AC 128 ms 10860 KB
subtask01-24.txt AC 167 ms 15468 KB
subtask01-25.txt WA 167 ms 14828 KB