제출 #368397

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
368397		8e7	시간이 돈 (balkan11_timeismoney)	C++14	100 / 100	144 ms	1536 KiB

timeismoney

//Challenge: Accepted
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <utility>
#include <queue>
#define ll long long
#define pii pair<int, int>
#define ff first
#define ss second
#define maxn 25005
using namespace std;
struct edge{
	int to = 0, t = 0, c = 0;
	edge(int x, int z, int w) {
		to = x, t = z, c = w;
	}
	edge();
};
vector<edge> adj[maxn];
vector<pii> hull, slope, ed;
const int inf = 1<<30;
pii mst(int n, int A, int B, bool getans) {
	pii ret = make_pair(0, 0);
	int mind[n], from[n];
	pii save[n];
	bool found[n];
	for (int i = 0;i < n;i++) mind[i] = inf, found[i] = false, from[i] = -1;
	mind[0] = 0;
	save[0] = make_pair(0, 0);
	for (int cnt = 0;cnt < n;cnt++) {
		int mi = inf, ind = 0;
		for (int i = 0;i < n;i++) {
			if (!found[i] && mind[i] < mi) {
				mi = mind[i];
				ind = i;
			}
		}
		ret.ff += save[ind].ff, ret.ss += save[ind].ss;
		if (getans && from[ind] != -1) ed.push_back(make_pair(ind, from[ind]));
		found[ind] = true;
		mind[ind] = 0;
		for (edge ed:adj[ind]) {
			int nv = A * ed.t + B * ed.c;
			if (nv < mind[ed.to]) {
				mind[ed.to] = nv;
				from[ed.to] = ind;
				save[ed.to] = make_pair(ed.t, ed.c);
			}
		}
	}
	return ret;
}
void solve(int n, pii lef, pii rig) {
	//cout << lef.ff << " " << lef.ss << " " << rig.ff << " " << rig.ss << endl;
	int xdif = rig.ff - lef.ff, ydif = lef.ss - rig.ss;
	pii mid = mst(n, ydif, xdif, false);
	if (mid != lef && mid != rig && ydif * mid.ff + xdif * mid.ss < ydif * lef.ff + xdif * lef.ss) {
		slope.push_back(make_pair(ydif, xdif));
		hull.push_back(mid);
		solve(n, lef, mid);
		solve(n, mid, rig);
	}
}
int main() {
	ios_base::sync_with_stdio(0);cin.tie(0);
	int n, m;
	cin >> n >> m;
	for (int i = 0;i < m;i++) {
		int a, b, t, c;
		cin >> a >> b >> t >> c;
		adj[a].push_back(edge(b, t, c));
		adj[b].push_back(edge(a, t, c));
	}
	pii lef = mst(n, 1, 0, false), rig = mst(n, 0, 1, false);
	hull.push_back(lef), hull.push_back(rig);
	slope.push_back(make_pair(1, 0)), slope.push_back(make_pair(0, 1));
	solve(n, lef, rig);
	int ans = inf;
	pii out, sl;
	for (int i = 0;i < hull.size();i++) {
		if (hull[i].ff * hull[i].ss < ans) {
			ans = hull[i].ff * hull[i].ss;
			out = hull[i];
			sl = slope[i];
		}
	}
	cout << out.ff << " " << out.ss << "\n";
	mst(n, sl.ff, sl.ss, true);
	for (auto i:ed) cout << i.ff << " " << i.ss << "\n";
}
/*
5 7
0 1 161 79
0 2 161 15
0 3 13 153
1 4 142 183
2 4 236 80
3 4 40 241
2 1 65 92
 */

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

timeismoney.cpp: In function 'int main()':
timeismoney.cpp:82:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |  for (int i = 0;i < hull.size();i++) {
      |                 ~~^~~~~~~~~~~~~

• Subtask 1: 100 / 100