답안 #640862

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
640862	2022-09-15T11:49:38 Z	SanguineChameleon	시간이 돈 (balkan11_timeismoney)	C++17	컴파일 오류	0 ms	0 KB

timeismoney

// BEGIN BOILERPLATE CODE

#include <bits/stdc++.h>
using namespace std;

#ifdef KAMIRULEZ
	const bool kami_loc = true;
	const long long kami_seed = 69420;
#else
	const bool kami_loc = false;
	const long long kami_seed = chrono::steady_clock::now().time_since_epoch().count();
#endif

const string kami_fi = "kamirulez.inp";
const string kami_fo = "kamirulez.out";
mt19937_64 kami_gen(kami_seed);

long long rand_range(long long rmin, long long rmax) {
	uniform_int_distribution<long long> rdist(rmin, rmax);
	return rdist(kami_gen);
}

void file_io(string fi, string fo) {
	if (fi != "" && (!kami_loc || fi == kami_fi)) {
		freopen(fi.c_str(), "r", stdin);
	}
	if (fo != "" && (!kami_loc || fo == kami_fo)) {
		freopen(fo.c_str(), "w", stdout);
	}
}

void set_up() {
	if (kami_loc) {
		file_io(kami_fi, kami_fo);
	}
	ios_base::sync_with_stdio(0);
	cin.tie(0);
}

void just_do_it();

void just_exec_it() {
	if (kami_loc) {
		auto pstart = chrono::steady_clock::now();
		just_do_it();
		auto pend = chrono::steady_clock::now();
		long long ptime = chrono::duration_cast<chrono::milliseconds>(pend - pstart).count();
		string bar(50, '=');
		cout << '\n' << bar << '\n';
		cout << "Time: " << ptime << " ms" << '\n';
	}
	else {
		just_do_it();
	}
}

int main() {
	set_up();
	just_exec_it();
	return 0;
}

// END BOILERPLATE CODE

// BEGIN MAIN CODE

const int ms = 1e4 + 20;
const int st = 2e2 + 20;
int de[st];
int par[st];
long long res = (long long)1e18 + 20;
long long fa;
long long fb;
int n, m;

struct point {
	long long x, y;
};

point fp;

int root(int u) {
	if (!par[u]) {
		return u;
	}
	return root(par[u]);
}

bool update(int u, int v) {
	int ru = root(u);
	int rv = root(v);
	if (ru == rv) {
		return false;
	}
	if (de[ru] > de[rv]) {
		swap(ru, rv);
	}
	par[ru] = rv;
	if (de[ru] == de[rv]) {
		de[rv]++;
	}
	return true;
}

struct edge {
	int u, v;
	long long x, y;
};

struct cmp {
	long long pa;
	long long pb;
	cmp(long long a, long long b) {
		pa = a;
		pb = b;
	}
	bool operator()(edge e1, edge e2) {
		return e1.x * pa + e1.y * pb < e2.x * pa + e2.y * pb;
	}
};

edge e[ms];

point mst(long long a, long long b, bool f = false) {
	long long sx = 0;
	long long sy = 0;
	for (int i = 0; i < n; i++) {
		de[i] = 0;
		par[i] = 0;
	}
	sort(e, e + m, cmp(a, b));
	for (int i = 0; i < m; i++) {
		int u = e[i].u;
		int v = e[i].v;
		if (update(u, v)) {
			if (f) {
				cout << u << " " << v << '\n';
			}
			sx += e[i].x;
			sy += e[i].y;
		}
	}
	long long cr = sx * sy;
	if (cr < res) {
		res = cr;
		fp = point(sx, sy);
		fa = a;
		fb = b;
	}
	return point(sx, sy);
}

void solve(point p1, point p2) {
	if (p1.x == p2.x || p1.y == p2.y) {
		return;
	}
	long long dx = p2.x - p1.x;
	long long dy = p1.y - p2.y;
	point p3 = mst(dy, dx);
	if ((p1.y - p2.y) * (p3.x - p1.x) == (p1.y - p3.y) * (p2.x - p1.x)) {
		return;
	}
	solve(p1, p3);
	solve(p3, p2);
}

void just_do_it() {
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		cin >> e[i].u >> e[i].v >> e[i].x >> e[i].y;
	}
	solve(mst(1, 0), mst(0, 1));
	cout << fp.x << " " << fp.y << '\n';
	mst(fa, fb, 1);
}

// END MAIN CODE

Compilation message

timeismoney.cpp: In function 'point mst(long long int, long long int, bool)':
timeismoney.cpp:146:20: error: no matching function for call to 'point::point(long long int&, long long int&)'
  146 |   fp = point(sx, sy);
      |                    ^
timeismoney.cpp:76:8: note: candidate: 'point::point()'
   76 | struct point {
      |        ^~~~~
timeismoney.cpp:76:8: note:   candidate expects 0 arguments, 2 provided
timeismoney.cpp:76:8: note: candidate: 'constexpr point::point(const point&)'
timeismoney.cpp:76:8: note:   candidate expects 1 argument, 2 provided
timeismoney.cpp:76:8: note: candidate: 'constexpr point::point(point&&)'
timeismoney.cpp:76:8: note:   candidate expects 1 argument, 2 provided
timeismoney.cpp:150:21: error: no matching function for call to 'point::point(long long int&, long long int&)'
  150 |  return point(sx, sy);
      |                     ^
timeismoney.cpp:76:8: note: candidate: 'point::point()'
   76 | struct point {
      |        ^~~~~
timeismoney.cpp:76:8: note:   candidate expects 0 arguments, 2 provided
timeismoney.cpp:76:8: note: candidate: 'constexpr point::point(const point&)'
timeismoney.cpp:76:8: note:   candidate expects 1 argument, 2 provided
timeismoney.cpp:76:8: note: candidate: 'constexpr point::point(point&&)'
timeismoney.cpp:76:8: note:   candidate expects 1 argument, 2 provided
timeismoney.cpp: In function 'void file_io(std::string, std::string)':
timeismoney.cpp:25:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |   freopen(fi.c_str(), "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
timeismoney.cpp:28:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   28 |   freopen(fo.c_str(), "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~