oj.uz

Submission #322625

# Submission time Handle Problem Language Result Execution time Memory
322625 2020-11-15T03:57:21 Z denverjin timeismoney (balkan11_timeismoney) C++14
0 / 100
 501 ms 932 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define mp make_pair
#define pb push_back

#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#define rep(i, n) for (int i = 0; i < (int)(n); ++ i)

struct Edge {
    int u, v, a, b, c;
    Edge(int u, int v, int a, int b, int c):
        u(u), v(v), a(a), b(b), c(c) {}
    bool operator < (const Edge &o) const {
        return c != o.c ? c < o.c : (a != o.a ? a < o.a : b < o.b);
    }
};

struct Point {
    int x, y;
    Point(): x(), y() {}
    Point(int x, int y): x(x), y(y) {}
    bool operator < (const Point &o) const {
        return x != o.x ? x < o.x : y < o.y;
    }
    bool operator == (const Point &o) const {
        return x == o.x && y == o.y;
    }
    friend ostream &operator << (ostream &o, Point x) {
        return o << "(" << x.x << ", " << x.y << ")";
    }
};

struct UnionFind {
    vector <int> fa;
    UnionFind(int n): fa(n) {
        rep(i, n) fa[i] = i;
    }
    int find(int x) {
        return x == fa[x] ? x : fa[x] = find(fa[x]);
    }
    bool merge(int x, int y) {
        x = find(x), y = find(y);
        if (x == y) return 0;
        fa[x] = y;
        return 1;
    }
};

int n, m;
vector <Edge> E;
pair <int, Point> ans(0x3f3f3f3f, Point());

Point kruskal(int ka, int kb) {
    rep(i, m) E[i].c = E[i].a * ka + E[i].b * kb;
    sort(E.begin(), E.end());
    Point ans;
    UnionFind uf(n);
    rep(i, m) {
        if (uf.merge(E[i].u, E[i].v)) {
            ans.x += E[i].a;
            ans.y += E[i].b;
        }
    }
    return ans;
}

void solve(Point A, Point B) {
    ans = min(ans, mp(A.x * A.y, A));
    ans = min(ans, mp(B.x * B.y, B));
    if (A.x > B.x || A.y < B.y) return ;
    Point C = kruskal(-(B.y - A.y), B.x - A.x);
    if (C == A || C == B) return ;
    solve(A, C); solve(C, B);
}

int main() {
    cin >> n >> m;
    rep(i, m) {
        int u, v, a, b;
        cin >> u >> v >> a >> b;
        E.pb(Edge(u, v, a, b, 0));
    }
    Point A = kruskal(1, 0);
    Point B = kruskal(0, 1);
    solve(A, B);
    cout << ans.second.x << " " << ans.second.y << endl;
    return 0;
}

Subtask #1
0.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 364 KB Unexpected end of file - int32 expected
2 Incorrect 1 ms 364 KB Unexpected end of file - int32 expected
3 Incorrect 1 ms 364 KB Unexpected end of file - int32 expected
4 Incorrect 1 ms 364 KB Unexpected end of file - int32 expected
5 Incorrect 1 ms 364 KB Unexpected end of file - int32 expected
6 Incorrect 1 ms 364 KB Unexpected end of file - int32 expected
7 Incorrect 3 ms 364 KB Unexpected end of file - int32 expected
8 Incorrect 11 ms 844 KB Unexpected end of file - int32 expected
9 Incorrect 1 ms 364 KB Unexpected end of file - int32 expected
10 Incorrect 1 ms 372 KB Unexpected end of file - int32 expected
11 Incorrect 1 ms 364 KB Unexpected end of file - int32 expected
12 Incorrect 1 ms 364 KB Unexpected end of file - int32 expected
13 Incorrect 1 ms 364 KB Unexpected end of file - int32 expected
14 Incorrect 5 ms 364 KB Unexpected end of file - int32 expected
15 Incorrect 4 ms 364 KB Unexpected end of file - int32 expected
16 Incorrect 62 ms 492 KB Unexpected end of file - int32 expected
17 Incorrect 61 ms 364 KB Unexpected end of file - int32 expected
18 Incorrect 59 ms 364 KB Unexpected end of file - int32 expected
19 Incorrect 489 ms 932 KB Unexpected end of file - int32 expected
20 Incorrect 501 ms 932 KB Unexpected end of file - int32 expected