제출 #585568

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
585568		1ne	전선 연결 (IOI17_wiring)	C++14	0 / 100	1096 ms	204988 KiB

wiring

#include "wiring.h"
#include<bits/stdc++.h>
using namespace std;
struct node{
	long long u,v,cost;	
};
struct DSU{
	vector<int>parent;
	vector<int>sz;
	void build(int n){
		parent.resize(n);
		sz.resize(n);
		for (int i = 0;i<n;++i){
			parent[i] = i;
			sz[i] = 1;
		}
	}
	int findsets(int v){
		if (v == parent[v])return v;
		parent[v] = findsets(parent[v]);
		return parent[v];
	}
	bool unionset(int a,int b){
		int u = findsets(a);
		int v = findsets(b);
		if (u == v)return false;
		if (sz[u] < sz[v])swap(u,v);
		parent[v] = u;
		sz[u]+=sz[v];
		return true;
	}
};
long long min_total_length(std::vector<int> r, std::vector<int> b) {
	vector<node>edge;
	map<int,int>deg;
	long long ans = 0;
	for (auto x:r){
		for (auto y:b){
			edge.push_back({x,y,abs(x - y)});
			deg[x]++;
			deg[y]++;
			ans+=abs(x - y);
		}
	}
	sort(edge.begin(),edge.end(),[&](auto x,auto y){
		return x.cost > y.cost;
	});
	for (auto x:edge){
		if (deg[x.u] > 1 && deg[x.v] > 1){
			deg[x.u]--;
			deg[x.v]--;
			ans-=x.cost;
		}
	}
	return ans;
}

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