Submission #101777

#TimeUsernameProblemLanguageResultExecution timeMemory
101777daniel920712전선 연결 (IOI17_wiring)C++14
0 / 100
3 ms384 KiB
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <map>
#include <utility>
#include <vector>
#include <algorithm>
#include "wiring.h"

using namespace std;
pair < long long , pair < int , int > > all[1000005];
bool F(pair < long long , pair < int , int > > a,pair < long long , pair < int , int > > b)
{
    return a<b;
}
int father[200005];
int Find(int here)
{
    if(father[here]==here) return here;
    else
    {
        father[here]=Find(father[here]);
        return father[here];
    }
}

long long min_total_length(vector < int > r, vector < int > b)
{
    int N=r.size();
    int M=b.size();
    int i,j,now=0;
    long long ans=0;
    for(i=0;i<N;i++) for(j=0;j<M;j++) all[now++]=make_pair(abs(r[i]-b[j]),make_pair(i,j+N));
    for(i=0;i<N+M;i++) father[i]=i;
    sort(all,all+now,F);
    for(i=0;i<now;i++)
    {

        if(Find(all[i].second.first)!=Find(all[i].second.second))
        {
            ans+=all[i].first;
            father[Find(all[i].second.first)]=Find(all[i].second.second);
        }
    }

    return ans;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...