제출 #216969

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
216969		davitmarg	전선 연결 (IOI17_wiring)	C++17	0 / 100	5 ms	384 KiB

wiring

/*DavitMarg*/
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstring>
#include <map>
#include <unordered_map>
#include <set>
#include <queue>
#include <iomanip>
#include <bitset>
#include <stack>
#include <cassert>
#include <iterator>
#include <fstream>
#include "wiring.h"
#define mod 1000000007ll
#define LL long long
#define LD long double
#define MP make_pair
#define PB push_back
#define all(v) v.begin(), v.end()
using namespace std;

const int N = 100005;

vector<pair<int, int>> a;
vector<pair<LL, pair<int,int>>> e;
pair<int, int> last[2];
int n, p[N];

int get(int v)
{
	if (v == p[v])
		return v;
	return p[v] = get(p[v]);
}

void dsu(int a, int b)
{
	a = get(a);
	b = get(b);
	if (a == b)
		return;
	p[b] = a;
}

LL min_total_length(vector<int> r, vector<int> b)
{
	for (int i = 0; i < r.size(); i++)
		a.push_back(MP(r[i], i + 1));
	for (int i = 0; i < b.size(); i++)
		a.push_back(MP(b[i], r.size() + i + 1));
	n = r.size() + b.size();
	sort(all(a));

	last[0] = last[1] = MP(0,0);
	for (int i = 0; i < a.size(); i++)
	{
		int col = a[i].second<=r.size();
		int pos = a[i].first;

		last[col] = a[i];
		if (last[!col].second)
			e.push_back(MP(last[col].first - last[!col].first, MP(last[col].second, last[!col].second)));
	}

	last[0] = last[1] = MP(0, 0);
	reverse(all(a));
	for (int i = 0; i < a.size(); i++)
	{
		int col = a[i].second <= r.size();
		int pos = a[i].first;

		last[col] = a[i];
		if (last[!col].second)
			e.push_back(MP(last[!col].first - last[col].first, MP(last[col].second, last[!col].second)));
	}

	sort(all(e));
	for (int i = 1; i <= n; i++)
		p[i] = i;
	LL ans = 0;
	for (int i = 0; i < e.size(); i++)
	{
		int a = e[i].second.first;
		int b = e[i].second.second;
		LL d = e[i].first;
		if (get(a) != get(b))
		{
			ans += d;
			dsu(a, b);
		}
	}
	return ans;
}



/*

3 3
4
0 0
0 1
0 2
1 1
0 0

2 3
2
0 0
0 1
3 3
4
0 0
0 1
0 2
1 1
3 3
5
0 0
1 0
1 2
2 1
2 2
0 0


*/

컴파일 시 표준 에러 (stderr) 메시지

wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:52:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < r.size(); i++)
                  ~~^~~~~~~~~~
wiring.cpp:54:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < b.size(); i++)
                  ~~^~~~~~~~~~
wiring.cpp:60:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < a.size(); i++)
                  ~~^~~~~~~~~~
wiring.cpp:62:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   int col = a[i].second<=r.size();
wiring.cpp:63:7: warning: unused variable 'pos' [-Wunused-variable]
   int pos = a[i].first;
       ^~~
wiring.cpp:72:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < a.size(); i++)
                  ~~^~~~~~~~~~
wiring.cpp:74:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   int col = a[i].second <= r.size();
wiring.cpp:75:7: warning: unused variable 'pos' [-Wunused-variable]
   int pos = a[i].first;
       ^~~
wiring.cpp:86:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < e.size(); i++)
                  ~~^~~~~~~~~~

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