Submission #73254

#	Time	Username	Problem	Language	Result	Execution time	Memory
73254		nvmdava	전선 연결 (IOI17_wiring)	C++17	0 / 100	3 ms	468 KiB

wiring

#include "wiring.h"
#define INF 2000000005
#include <bits/stdc++.h>
using namespace std;
struct Path{
	int r, b, len;
	Path(int _r, int _b, int _len){
		r = _r;
		b = _b;
		len = _len;
	}
	bool operator<(const Path& rhs) const{
		return len < rhs.len;
	}
};

vector<Path> v;

int rr[100007], bb[100007];
int conr[100007], conb[100007];
long long min_total_length(std::vector<int> r, std::vector<int> b) {
	
	r.push_back(INF);
	b.push_back(INF);
	
	bb[0] = 0;
	rr[0] = 0;
	long long ans = 0;
	
	for(int i = 1; i < b.size(); i++){
		bb[i] = upper_bound(r.begin() + bb[i - 1], r.end(), (b[i] + b[i - 1]) / 2) - r.begin();
	}
	for(int i = 1; i < r.size(); i++){
		rr[i] = upper_bound(b.begin() + rr[i - 1], b.end(), (r[i] + r[i - 1]) / 2) - b.begin();
	}
	
	for(int i = 0; i < b.size(); i++){
		for(int j = bb[i]; j < bb[i + 1]; j++){
			v.push_back(Path(j, i, abs(r[j] - b[i])));
		}
	}
	for(int i = 0; i < r.size(); i++){
		for(int j = rr[i]; j < rr[i + 1]; j++){
			v.push_back(Path(i, j, abs(r[i] - b[j])));
		}
	}
	sort(v.begin(), v.end());
	
	for(auto x : v){
		if(conr[x.r] * conb[x.b] == 0){
			conr[x.r]++;
			conb[x.b]++;
			ans += x.len;
		}
	}
	
	return ans;
}

Compilation message (stderr)

wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:30:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 1; i < b.size(); i++){
                 ~~^~~~~~~~~~
wiring.cpp:33:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 1; i < r.size(); i++){
                 ~~^~~~~~~~~~
wiring.cpp:37:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < b.size(); i++){
                 ~~^~~~~~~~~~
wiring.cpp:42:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < r.size(); i++){
                 ~~^~~~~~~~~~

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