Submission #426486

#	Time	Username	Problem	Language	Result	Execution time	Memory
426486		jeqcho	Wiring (IOI17_wiring)	C++17	0 / 100	4 ms	4940 KiB

wiring

#include "wiring.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<pii> vpi;

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define F0R(i,b) FOR(i,0,b)
#define ROF(i,a,b) for(int i=(b)-1;i>=(a);--i)
#define R0F(i,b) ROF(i,0,b)
#define all(x) begin(x),end(x)
#define sz(x) int(x.size())
#define pb push_back
#define rsz resize
#define trav(a,x) for(auto&a :x)
#define fi first
#define se second

int const N=1e5+3;
// whether a node is visited, identify by id
bitset<2*N>vis;
vpi adj[2*N];
ll dp[2*N][2];
bool safe=0;
ll mn=4e18;

bool isleaf(int now,int par)
{
	// guaranteed tree size >1
	if(sz(adj[now])==1 && adj[now][0].fi==par)return 1;
	return 0;
}

void dfs(int now,int par,int w)
{
	trav(chi,adj[now])
	{
		if(chi.fi==par)continue;
		dfs(chi.fi,now,chi.se);
	}
	dp[now][1]=w;
	if(isleaf(now,par))dp[now][1]=-2e18;
	trav(chi,adj[now])
	{
		if(chi.fi==par)continue;
		dp[now][1]+=dp[chi.fi][0];
	}
	dp[now][0]=0;
	trav(chi,adj[now])
	{
		if(chi.fi==par)continue;
		dp[now][0]+=max(dp[chi.fi][1],dp[chi.fi][0]);
		if(now==0)
		{
			if(dp[chi.fi][0]>=dp[chi.fi][1])
				safe=1;
			mn=min(mn,dp[chi.fi][1]);
		}
		
	}
}

ll min_total_length(vi r, vi b) {
	priority_queue<pair<int,pii>>q;
	q.push({0,{0,-1}});
	ll sum=0;
	while(!q.empty())
	{
		int w1 = -q.top().fi;
		int u = q.top().se.fi;
		int par = q.top().se.se;
		q.pop();
		if(vis[u])continue;
		vis[u]=1;
		sum+=w1;
		if(par!=-1)
		{
			adj[par].pb({u,w1});
			adj[u].pb({par,w1});
		}
		if(u>=sz(r))
		{
			// blue
			F0R(i,sz(r))
			{
				if(vis[i])continue;
				int w = abs(b[u-sz(r)]-r[i]);
				q.push({-w,{i,u}});
			}
		}
		else
		{
			// red
			F0R(i,sz(b))
			{
				if(vis[i+sz(r)])continue;
				int w = abs(r[u]-b[i]);
				q.push({-w,{i+sz(r),u}});
			}
		}
	}
	dfs(0,-1,0);
	ll cand = dp[0][1];
	if(safe)cand=max(cand,dp[0][0]);
	else cand=max(cand,dp[0][0]-mn);
	return sum-cand;
}

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