Submission #767381

#	Time	Username	Problem	Language	Result	Execution time	Memory
767381		APROHACK	Wiring (IOI17_wiring)	C++14	0 / 100	20 ms	8436 KiB

wiring

#include "wiring.h"
#include <bits/stdc++.h>
#define pb push_back
#define pos first
#define color second
#define ll long long
using namespace std;
vector<pair<ll, bool> >nodes;
ll distNext[200001]; // Distancia de este nodo con el siguiente de otro color
ll distanciaAcum[200005]; // distancia acumulada si tomo desde i y lo uno con el siguiente del otro color
int siguiente[200005]; // siguiente del otro color

int nm;
ll mem[200005];

ll dp(int node){
	int last;
	ll ret = 0;
	if(siguiente[node] == -1)return LLONG_MAX;
	if(mem[node] != -1)return mem[node];
	if(siguiente[siguiente[node]] == -1){
		// Tengo que unir este grupo con todos los de alla.
		last = nm-1;
		ret = distanciaAcum[node];
		int numNodos = siguiente[node]-node;
		ll acum2 = 0, cuenta = 1;
		for(int i = siguiente[node] + 1 ; i <= last ; i ++){
			cuenta ++;
			
			if(cuenta <= numNodos){
				acum2+= nodes[i].pos-nodes[i-1].pos;
				ret += acum2;
			}
			else{
				acum2 += nodes[i].pos - nodes[siguiente[node]-1].pos;
				ret += acum2 ;
			}
		}
	}else{
		ret = distanciaAcum[node] + dp(siguiente[node]);
		if(dp(siguiente[node] +1) != LLONG_MAX){
			ret = min(ret, distanciaAcum[node] + dp(siguiente[node]+1));
		}
		int numNodos = siguiente[node]-node;
		ll acum2 = 0, cuenta = 1;
		for(int i = siguiente[node]+1 ; i < siguiente[siguiente[node]] ; i++){
			cuenta ++;
			
			if(cuenta <= numNodos && dp(i+1) != LLONG_MAX){
				acum2+= nodes[i].pos-nodes[i-1].pos;
				ret = min(ret, distanciaAcum[node] + acum2 + dp(i+1));
			}
			else{
				acum2 += nodes[i].pos - nodes[siguiente[node]-1].pos;
				if(dp(i+1) != LLONG_MAX){
					ret = min(ret, distanciaAcum[node] + acum2 + dp(i+1));
				}
			}
		}
	}
	return mem[node] = ret;
}

long long min_total_length(std::vector<int> r, std::vector<int> b) {
	memset(mem, -1, sizeof mem);
	int ir = r.size() -1, ib = 0;
	ll ans = 0;
	nm = r.size() + b.size();
	for(auto i : r)nodes.pb({i, 0});
	for(auto i : b)nodes.pb({i, 1});
	sort(nodes.begin(), nodes.end());
	ll last0 = -1, last1 = -1;
	int ultimo0 = -1, ultimo1 = -1;
	for(int i = nm-1 ; i >= 0 ; i --){
		if(nodes[i].color == 0){
			//cout << 0 << " ";
			if(last1-nodes[i].pos < 0){
				distNext[i] = -1;
			}else{
				distNext[i] = last1-nodes[i].pos;
			}
			last0 = nodes[i].pos;
			ultimo0 = i;
			siguiente[i] = ultimo1;
		}else{
			//cout << 1 << " ";
			if(last0-nodes[i].pos < 0){
				distNext[i] = -1;
			}else{
				distNext[i] = last0-nodes[i].pos;
			}
			last1 = nodes[i].pos;
			ultimo1 = i;
			siguiente[i] = ultimo0;
		}
		
	}
	ll distCum[2];
	distCum[0] = 0;
	distCum[1] = 0;
	for(int i = nm-1 ; i >= 0 ; i --){
		if(distNext[i] != -1){
			distCum[nodes[i].color] += distNext[i];
			distanciaAcum[i] = distCum[nodes[i].color];
		}else distanciaAcum[i] = -1;
		if(nodes[i].color == 0)distCum[1] = 0;
		else distCum[0] = 0;
	}
	
	//for(int i = 0 ; i < nm ; i ++)cout << dp(i) << endl;
	
	
	return dp(0);
}

Compilation message (stderr)

wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:66:6: warning: unused variable 'ir' [-Wunused-variable]
   66 |  int ir = r.size() -1, ib = 0;
      |      ^~
wiring.cpp:66:24: warning: unused variable 'ib' [-Wunused-variable]
   66 |  int ir = r.size() -1, ib = 0;
      |                        ^~
wiring.cpp:67:5: warning: unused variable 'ans' [-Wunused-variable]
   67 |  ll ans = 0;
      |     ^~~

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