Submission #584696

#	Time	Username	Problem	Language	Result	Execution time	Memory
584696		1ne	Wiring (IOI17_wiring)	C++14	0 / 100	1 ms	300 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<pair<int,int>>arr;
	for (auto x:r){
		arr.push_back({x,0});
	}
	for (auto x:b){
		arr.push_back({x,1});
	}
	map<long long,long long>minny;
	vector<node>edge;
	long long rr = -1,bb = -1;
	sort(arr.begin(),arr.end());
	for (auto x:arr){
		if (x.second == 0){
			if (bb!=-1){
				edge.push_back({x.first,bb,x.first - bb});
				minny[x.first] = x.first - bb;
			}
			
			rr = x.first;
		}
		else{
			if (rr!=-1){
				edge.push_back({x.first,rr,x.first - rr});
				minny[x.first] = x.first - rr;
			}
			bb = x.first;
		}
	}
	sort(arr.rbegin(),arr.rend());
	rr = -1,bb =-1;
	for (auto x:arr){
		if (x.second == 0){
			if (bb!=-1){
				edge.push_back({x.first,bb,bb - x.first});
				minny[x.first] = min(minny[x.first],bb - x.first);
			}
			rr = x.first;
		}
		else{
			if (rr!=-1){
				edge.push_back({x.first,rr,rr - x.first});
				minny[x.first] = min(minny[x.first],rr - x.first);
			}
			bb = x.first;
		}
	}
	sort(edge.begin(),edge.end(),[&](auto x,auto y){
		return x.cost < y.cost;
	});
	map<long long,bool>mp;
	int64_t ans = 0;
	for (auto x:edge){
		if (!mp[x.u] && !mp[x.v]){
			mp[x.u] = true;
			mp[x.v] = true;
			ans+=x.cost;
		}
	}
	set<int>brr;
	for (auto x:b){
		if (!mp[x]){
			brr.insert(x);
		}
	}
	const long long maxn = 1e15;
	for (auto x:r){
		if (!mp[x]){
			int64_t dist = maxn;
			int64_t index = maxn;
			for (auto y:brr){
				if (y - x<dist){
					index = y;
					dist = y - x;
				}
			}
			if (index ==maxn){
				ans+=minny[x];
			}
			else if (minny[x] + minny[index] < dist){
				ans+=minny[x];
			}
			else{
				ans+=dist;
				brr.erase(index);
			}
		}
	}
	for (auto x:brr)ans+=minny[x];
	return ans;
}

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