Submission #3399326


Source Code Expand

Copy
#include <bits/stdc++.h>
#define MOD 998244353
using namespace std;

set<pair<pair<long long,long long> ,long long> > X;
set<pair<pair<long long,long long> ,long long> > Y;
long long ans;
int a[100005];int b[100005];
int main(){
    int n;cin >> n;
    for(int i=1;i<=n;++i){
        scanf("%d %d",&a[i],&b[i]);X.insert(make_pair(make_pair(a[i],b[i]),i));
        Y.insert(make_pair(make_pair(b[i],a[i]),i));
    }
    while(X.size()!=1){

        auto it=X.begin();auto ip=Y.begin();

        if((*it).first.first<=(*ip).first.first){
            auto wh=Y.end();--wh;
            //if((*wh).second==(*it).second) --wh;
            ans+=min((*it).first.first,(*wh).first.first);
            auto qw=make_pair(make_pair((*wh).first.second,(*it).first.second),(*it).second);
            auto qv=make_pair(make_pair((*it).first.second,(*wh).first.second),(*it).second);
            auto tq=(*it);
            auto tv=(*wh);
            X.erase(it);Y.erase(wh);Y.erase(make_pair(make_pair(tq.first.second,tq.first.first),tq.second));
            X.erase(make_pair(make_pair(tv.first.second,tv.first.first),tv.second));
            X.insert(qw);Y.insert(qv);
        }
        else{
            auto wh=X.end();--wh;
           // if((*wh).second==(*ip).second) --wh;
            ans+=min((*ip).first.first,(*wh).first.first);
            auto qw=make_pair(make_pair((*ip).first.second,(*wh).first.second),(*ip).second);
            auto qv=make_pair(make_pair((*wh).first.second,(*ip).first.second),(*ip).second);
            auto tq=(*wh);
            auto tv=(*ip);
            X.erase(wh);Y.erase(ip);Y.erase(make_pair(make_pair(tq.first.second,tq.first.first),tq.second));
            X.erase(make_pair(make_pair(tv.first.second,tv.first.first),tv.second));
            X.insert(qw);Y.insert(qv);
        }
    }
    auto it=X.begin();
    ans+=min((*it).first.first,(*it).first.second);
    //auto ip=Y.begin();
    //assert(min((*ip).first.first,(*ip).first.second)==min((*it).first.first,(*it).first.second));
    cout << ans << endl;


    return 0;
}

Submission Info

Submission Time
Task C - Min Cost Cycle
User sazerterus25
Language C++14 (GCC 5.4.1)
Score 0
Code Size 2109 Byte
Status

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:12:35: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d",&a[i],&b[i]);X.insert(make_pair(make_pair(a[i],b[i]),i));
                                   ^

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 sample-01.txt, sample-02.txt, sample-03.txt
All 0 / 700 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
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