Submission #49068

#	Time	Username	Problem	Language	Result	Execution time	Memory
49068		Namnamseo	Wiring (IOI17_wiring)	C++14	0 / 100	44 ms	6780 KiB

wiring

#include "wiring.h"
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using pp=pair<int,int>;

#define x first
#define y second

#define DBG if(0)

int n, m;
int pn;

pp pt[200010];
int sz[2];
int plst[2][100010];

int con[2][100010];
int aite[2][100010];
int wait[2][100010];

void build_pt(vector<int>& r, vector<int>& b){
	sz[0] = n = r.size();
	sz[1] = m = b.size();
	for(int i=0; i<n; ++i) plst[0][i]=r[i];
	for(int i=0; i<m; ++i) plst[1][i]=b[i];
	for(int ri=0; ri<2; ++ri){
		fill(con[ri], con[ri]+sz[ri], 0);
		fill(wait[ri], wait[ri]+sz[ri], 0);
	}
	pn = 0;
	for(int i=0, j=0; i<n || j<m;){
		if(i<n && (j==m || r[i]<b[j])){
			pt[pn].x = r[i];
			pt[pn].y = i;
			++pn; ++i;
		} else {
			pt[pn].x = b[j];
			pt[pn].y = n+j;
			++pn; ++j;
		}
	}
}

ll ans;

void connect1(int ri, bool force){
	int ss = sz[ri];
	for(int i=0; i<ss; ++i) if(!wait[ri][i] && !con[ri][i]){
		int mp = plst[ri][i];
		int jnxt = lower_bound(plst[ri^1], plst[ri^1]+sz[ri^1], mp) - plst[ri^1];
		int jbef = jnxt-1;
		int dnxt = (0<=jnxt && jnxt<sz[ri^1] ? abs(plst[ri^1][jnxt]-mp) : 2e9);
		int dbef = (0<=jbef && jbef<sz[ri^1] ? abs(plst[ri^1][jbef]-mp) : 2e9);
		if(dnxt == dbef){
			if(force){
				++con[ri][i]; aite[ri][i]=jbef;
				++con[ri^1][jbef]; aite[ri^1][jbef]=i;
				ans += dbef;
				DBG printf("c1%d %d,%d - %d,%d  ### cost %3d\n", force, ri, i, ri^1, jbef, dbef);
			}
		} else if(dnxt > dbef){
			++con[ri][i]; aite[ri][i]=jbef;
			++con[ri^1][jbef]; aite[ri^1][jbef]=i;
			ans += dbef;
			DBG printf("c1%d %d,%d - %d,%d  ### cost %3d\n", force, ri, i, ri^1, jbef, dbef);
		} else {
			++con[ri][i]; aite[ri][i]=jnxt;
			++con[ri^1][jnxt]; aite[ri^1][jnxt]=i;
			ans += dnxt;
			DBG printf("c1%d %d,%d - %d,%d  ### cost %3d\n", force, ri, i, ri^1, jnxt, dnxt);
		}
	}
}

void connect2(int ri){
	int ss = sz[ri];
	for(int i=0; i<ss; ++i) if(wait[ri][i] && !con[ri][i]){
		int mp = plst[ri][i];
		int jnxt = lower_bound(plst[ri^1], plst[ri^1]+sz[ri^1], mp) - plst[ri^1];
		int jbef = jnxt-1;
		int dnxt = (0<=jnxt && jnxt<sz[ri^1] ? abs(plst[ri^1][jnxt]-mp) : 2e9);
		int dbef = (0<=jbef && jbef<sz[ri^1] ? abs(plst[ri^1][jbef]-mp) : 2e9);
		if(con[ri^1][jnxt] == 1 && con[ri][aite[ri^1][jnxt]] >= 2){
			dnxt -= abs(plst[ri][aite[ri^1][jnxt]]-plst[ri^1][jnxt]);
		}
		if(con[ri^1][jbef] == 1 && con[ri][aite[ri^1][jbef]] >= 2){
			dbef -= abs(plst[ri][aite[ri^1][jbef]]-plst[ri^1][jbef]);
		}
		if(dnxt >= dbef){
			++con[ri][i]; aite[ri][i]=jbef;
			++con[ri^1][jbef]; aite[ri^1][jbef]=i;
			ans += dbef;
			DBG printf("c2n %d,%d - %d,%d  ### cost %3d\n", ri, i, ri^1, jbef, dbef);
		} else {
			++con[ri][i]; aite[ri][i]=jnxt;
			++con[ri^1][jnxt]; aite[ri^1][jnxt]=i;
			ans += dnxt;
			DBG printf("c2n %d,%d - %d,%d  ### cost %3d\n", ri, i, ri^1, jnxt, dnxt);
		}
	}
}

ll min_total_length(vector<int> r, vector<int> b) {
	build_pt(r, b);

	ans = 0;

	for(int i=2, p1=(pt[0].y>=n), p2=(pt[1].y>=n); i<pn; ++i){
		int p3=(pt[i].y>=n);
		if(p1==p2 && p2==p3){
			wait[p2][pt[i-1].y-p2*n] = 1;
		}
		p1=p2; p2=p3;
	}

	connect1(0, 0);
	connect1(1, 0);

	connect1(0, 1);
	connect1(1, 1);

	connect2(0);
	connect2(1);

	return ans;
}

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