oj.uz

답안 #39815

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
39815 2018-01-19T12:00:22 Z krauch 시간이 돈 (balkan11_timeismoney) C++14
100 / 100
 845 ms 2316 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pii;
#define SIZE(x) (int)((x).size())
inline int readi(){
	int x=0,f=1;char ch;ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
struct UnionFind {
	vector<int> data;
	void init(int n) { data.assign(n, -1); }
	bool unionSet(int x, int y) {
		x = root(x); y = root(y);
		if (x != y) {
			if (data[y] < data[x]) swap(x, y);
			data[x] += data[y]; data[y] = x;
		}
		return x != y;
	}
	int root(int x) { return data[x] < 0 ? x : data[x] = root(data[x]); }
};
struct edge {
	int x, y;
	int time, cost;
};
int A, B;
vector<edge> E;
bool cmp(const edge &a, const edge &b){
	return 1ll*a.time*A + 1ll*a.cost*B < 1ll*b.time*A + 1ll*b.cost*B;
}
ll cross(pii O, pii A, pii B){
    return 1ll*(A.first-O.first)*(B.second-O.second) - 1ll*(A.second-O.second)*(B.first-O.first);
}
int N, M, KEK;
vector<pii> lower_hull;
vector<pii> slopes;
vector<pii> ans;
pii bestmst;
pii mst(int a, int b, bool save) {
    ++KEK;
	assert(a>=0 && b>=0);
	A=a, B=b;
	sort(E.begin(),E.end(),cmp);
	UnionFind uf;
	uf.init(N);
	pii res = {0,0};
	for(int i=0; i<M; i++){
		if(uf.unionSet(E[i].x, E[i].y)){
			res.first += E[i].time;
			res.second += E[i].cost;
			if(save) ans.emplace_back(E[i].x, E[i].y);
		}
	}
	lower_hull.push_back(res);
	slopes.emplace_back(a,b);
	if(save) bestmst=res;
	return res;
}
void go(pii a, pii b) {
	pii p = mst(a.second-b.second,b.first-a.first,0);
	if(cross(p,a,b)==0) return;
	go(a,p); go(p,b);
}
int main() {
	N = readi();
	M = readi();
	E.resize(M);
	for(int i=0; i<M; i++){
		E[i].x = readi();
		E[i].y = readi();
		E[i].time = readi();
		E[i].cost = readi();
	}
	pii a = mst(1,0,0);
	pii b = mst(0,1,0);
	go(a, b);
	ll res = 1e18;
	for(pii p : lower_hull){
		res = min(res, p.first*p.second);
	}
	for(int i=0; i<SIZE(lower_hull); i++){
		if(lower_hull[i].first*lower_hull[i].second==res){
			mst(slopes[i].first, slopes[i].second, 1);
			break;
		}
	}
	assert(KEK <= 1000);
	printf("%lld %lld\n",bestmst.first,bestmst.second);
	for(pii p : ans){
		printf("%lld %lld\n",p.first,p.second);
	}
	return 0;
}

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 2024 KB Output is correct
2 Correct 0 ms 2024 KB Output is correct
3 Correct 0 ms 2024 KB Output is correct
4 Correct 0 ms 2024 KB Output is correct
5 Correct 0 ms 2024 KB Output is correct
6 Correct 0 ms 2024 KB Output is correct
7 Correct 1 ms 2024 KB Output is correct
8 Correct 2 ms 2184 KB Output is correct
9 Correct 0 ms 2024 KB Output is correct
10 Correct 0 ms 2024 KB Output is correct
11 Correct 0 ms 2024 KB Output is correct
12 Correct 0 ms 2024 KB Output is correct
13 Correct 1 ms 2024 KB Output is correct
14 Correct 6 ms 2024 KB Output is correct
15 Correct 4 ms 2024 KB Output is correct
16 Correct 92 ms 2168 KB Output is correct
17 Correct 95 ms 2168 KB Output is correct
18 Correct 90 ms 2168 KB Output is correct
19 Correct 845 ms 2316 KB Output is correct
20 Correct 835 ms 2316 KB Output is correct