Submission #585605

#	Time	Username	Problem	Language	Result	Execution time	Memory
585605		1ne	Wiring (IOI17_wiring)	C++14	0 / 100	1087 ms	262144 KiB

wiring

#include "wiring.h"
#include<bits/stdc++.h>
using namespace std;
struct node{
	long long u,v,cost;	
};
const int maxn = 200005;
long long min_total_length(std::vector<int> r, std::vector<int> b) {
	int n = (int)r.size();
	int m = (int)b.size();
	vector<pair<int,int>>arr;
	for (auto x:r){
		arr.push_back({x,0});
	}
	for (auto y:b){
		arr.push_back({y,1});
	}
	sort(arr.begin(),arr.end());
	vector<vector<int>>nxt(n + m,vector<int>(2,n + m)),prev(n + m,vector<int>(2,n + m));
	int rr = n + m,bb = n + m;
	for (int i = n + m - 1;i>=0;--i){
		nxt[i][0] = bb;
		nxt[i][1] = rr;
		if (arr[i].second == 0){
			rr = i;
		}
		else{
			bb = i;
		}
	}
	rr = -1,bb = -1;
	for (int i = 0;i<n + m;++i){
		prev[i][0] = bb;
		prev[i][1] = rr;
		if (arr[i].second == 0){
			rr = i;
		}
		else{
			bb = i;
		}
	}
	const long long MAX = 1e15;
	bitset<maxn>bit;
	unordered_map<bitset<maxn>,map<int,long long>>mp,vis;
	function<long long(int)>dfs = [&](int u){
		if (u == n + m){
			if (bit.count() == n + m)return 0LL;
			return MAX;
		}
		if (vis[bit][u])return mp[bit][u];
		long long ans = MAX;
		long long temp = 0;
		if (arr[u].second == 0){
			if (nxt[u][0]==n + m){
				temp = 0;
			}
			else{
				temp = arr[nxt[u][0]].first - arr[u].first;
				int temp1 = bit[u];
				int temp2 = bit[nxt[u][0]];
				bit[u] = 1;
				bit[nxt[u][0]] = 1;
				ans = min(ans,dfs(nxt[u][0]) + temp);
				bit[nxt[u][0]] = temp2;
				bit[u] = temp1;
			}
			ans = min(ans,dfs(min(nxt[u][0],nxt[u][1])));
			if (!bit[u] && prev[u][0]!=-1){
				int temp1 = bit[u];
				int temp2 = bit[prev[u][0]];
				bit[u] = true;
				bit[prev[u][0]] = true;
				ans = min(dfs(u) + arr[u].first - arr[prev[u][0]].first,ans);
				bit[prev[u][0]] = temp2;
				bit[u] = temp1;
			}
		}
		else{
			if (nxt[u][1]==n + m){
				temp = 0;
			}
			else{
				temp = arr[nxt[u][1]].first - arr[u].first;
				int temp1 = bit[u];
				int temp2 = bit[nxt[u][1]];
				bit[u] = 1;
				bit[nxt[u][1]] = 1;
				ans = min(ans,dfs(nxt[u][1]) + temp);
				bit[nxt[u][1]] = temp2;
				bit[u] = temp1;
			}
			ans = min(ans,dfs(min(nxt[u][0],nxt[u][1])));
			if (!bit[u] && prev[u][1]!=-1){
				int temp1 = bit[u];
				int temp2 = bit[prev[u][1]];
				bit[u] = true;
				bit[prev[u][1]] = true;
				ans = min(dfs(u) + arr[u].first - arr[prev[u][1]].first,ans);
				bit[prev[u][1]] = temp2;
				bit[u] = temp1;
			}
		}
		return mp[bit][u] = ans;
	};
	long long ans = dfs(0);
	return ans;
}

Compilation message (stderr)

wiring.cpp: In lambda function:
wiring.cpp:47:20: warning: comparison of integer expressions of different signedness: 'std::size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   47 |    if (bit.count() == n + m)return 0LL;
      |        ~~~~~~~~~~~~^~~~~~~~

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