# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
328242 | Mackerel_Pike | 시간이 돈 (balkan11_timeismoney) | C++14 | 6 ms | 1328 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
using namespace std;
#define FOR(i, x, y) for(int i = (x); i < (y); ++i)
#define REP(i, x, y) for(int i = (x); i <= (y); ++i)
#define PB push_back
#define MP make_pair
#define PH push
#define fst first
#define snd second
typedef long long ll;
typedef unsigned long long ull;
typedef double lf;
typedef long double Lf;
typedef pair<int, int> pii;
const int maxn = 255;
const int maxm = 10005;
int n, m;
int vis[maxn];
class Point{
public:
int x, y;
Point(){}
Point(int x_, int y_): x(x_), y(y_){}
inline bool operator == (const Point &oth)const{ return (x == oth.x && y == oth.y); }
inline int operator * (const Point &oth)const{ return x * oth.x + y * oth.y; }
inline Point operator * (const int &oth)const{ return Point(x * oth, y * oth); }
inline Point& operator += (const Point &oth){ x += oth.x, y += oth.y; return *this; }
inline Point& operator -= (const Point &oth){ x -= oth.x, y -= oth.y; return *this; }
inline Point operator - (const Point &oth)const{ Point ret = *this; ret -= oth; return ret; }
};
class Edge{
public:
int u, v;
Point val;
Edge(){}
Edge(int u_, int v_, Point val_): u(u_), v(v_), val(val_){}
} ed[maxm];
class Dsu{
private:
inline int find(int x){ return (x == fa[x]) ? x : (fa[x] = find(fa[x])); }
public:
int fa[maxn];
inline void init(){ FOR(i, 0, n) fa[i] = i; return; }
inline bool merge(int x, int y){
x = find(x), y = find(y);
if(x == y)
return false;
fa[x] = y;
return true;
}
} dsu;
inline Point kruscal(Point w){
vector<pii > vec;
FOR(i, 0, m)
vec.PB(MP(w * ed[i].val, i));
sort(vec.begin(), vec.end());
dsu.init();
Point ret(0, 0);
memset(vis, 0, sizeof(vis));
// printf("w = %d %d\n", w.x, w.y);
FOR(i, 0, vec.size()){
int id = vec[i].snd;
// printf("%d %d %d %d %d\n", vec[i].fst, ed[id].u, ed[i].v, ed[id].val.x, ed[id].val.y);
ret += ed[id].val * (vis[id] = dsu.merge(ed[id].u, ed[id].v));
}
return ret;
}
inline Point solve(Point A, Point B){
// printf("A = (%d %d) B = (%d %d)\n", A.x, A.y, B.x, B.y);
Point W = A - B; swap(W.x, W.y); W.x = -W.x;
Point C = kruscal(W);
Point P = ((C == A || C == B) ? A : solve(A, C)), Q = ((C == A || C == B) ? B : solve(C, B));
return (P.x * P.y < Q.x * Q.y ? P : Q);
}
int main(){
scanf("%d%d", &n, &m);
FOR(i, 0, m){
int u, v, t, c; scanf("%d%d%d%d", &u, &v, &t, &c);
ed[i] = Edge(u, v, Point(t, c));
}
Point A = kruscal(Point(0, 1));
Point B = kruscal(Point(1, 0));
Point C = solve(A, B);
kruscal(Point(C.y, C.x));
printf("%d %d\n", C.x, C.y);
FOR(i, 0, m) if(vis[i])
printf("%d %d\n", ed[i].u, ed[i].v);
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |