Submission #101777

#	Time	Username	Problem	Language	Result	Execution time	Memory
101777		daniel920712	Wiring (IOI17_wiring)	C++14	0 / 100	3 ms	384 KiB

wiring

#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;
}

• Subtask 1: 0 / 7
• Subtask 2: 0 / 13
• Subtask 3: 0 / 10
• Subtask 4: 0 / 25
• Subtask 5: 0 / 45