oj.uz

답안 #73254

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
73254 2018-08-28T06:01:45 Z nvmdava 전선 연결 (IOI17_wiring) C++17
0 / 100
 3 ms 468 KB 
#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

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.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 252 KB 3rd lines differ - on the 1st token, expected: '25859', found: '41560'
2 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 356 KB 3rd lines differ - on the 1st token, expected: '904', found: '946'
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 432 KB 3rd lines differ - on the 1st token, expected: '316', found: '356'
2 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 468 KB 3rd lines differ - on the 1st token, expected: '27', found: '29'
2 Halted 0 ms 0 KB -

Subtask #5
0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 252 KB 3rd lines differ - on the 1st token, expected: '25859', found: '41560'
2 Halted 0 ms 0 KB -