# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
37111 | Angelos | 시간이 돈 (balkan11_timeismoney) | C++11 | 633 ms | 2176 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <limits.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <algorithm>
#include <string>
#include <functional>
#include <vector>
#include <numeric>
#include <deque>
#include <bitset>
#include <iostream>
using namespace std;
typedef long long lint;
typedef long double llf;
typedef pair<int, int> pi;
struct edg{int s, e, x, y;}a[10005];
int n, m;
struct disj{
int pa[205];
void init(int n){
for(int i=0; i<n; i++) pa[i] = i;
}
int find(int x){
return pa[x] = (pa[x] == x ? x : find(pa[x]));
}
bool uni(int p, int q){
p = find(p), q = find(q);
if(p == q) return 0;
pa[q] = p; return 1;
}
}disj;
int cx = 1e9, cy = 1e9;
int mc1 = 1e9, mc2 = 1e9;
pi getmst(int c1, int c2, int p){
disj.init(n);
sort(a, a+m, [&](const edg &a, const edg &b){
return 1ll * c1 * a.x + 1ll * c2 * a.y < 1ll * c1 * b.x + 1ll * c2 * b.y;
});
pi tmp(0,0);
for(int i=0; i<m; i++){
if(disj.uni(a[i].s, a[i].e)){
tmp.first += a[i].x;
tmp.second += a[i].y;
if(p) printf("%d %d\n",a[i].s, a[i].e);
}
}
if(1ll * cx * cy > 1ll * tmp.first * tmp.second){
cx = tmp.first;
cy = tmp.second;
mc1 = c1, mc2 = c2;
}
return tmp;
}
bool ccw(pi a, pi b, pi c){
int dx1 = b.first - a.first;
int dy1 = b.second - a.second;
int dx2 = c.first - a.first;
int dy2 = c.second - a.second;
return 1ll * dx1 * dy2 >= 1ll * dy1 * dx2;
}
void solve(pi s, pi e){
pi m = getmst(s.second - e.second, e.first - s.first, 0);
if(!ccw(e, m, s)) solve(s, m), solve(m, e);
}
int main(){
cin >> n >> m;
for(int i=0; i<m; i++){
cin >> a[i].s >> a[i].e >> a[i].x >> a[i].y;
}
pi upper = getmst(1, 0, 0); // x is low
pi lower = getmst(0, 1, 0); // y is low
solve(upper, lower);
printf("%d %d\n",cx,cy);
getmst(mc1, mc2, 1);
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |