oj.uz

Submission #305680

# Submission time Handle Problem Language Result Execution time Memory
305680 2020-09-23T19:20:13 Z ntfx timeismoney (balkan11_timeismoney) C++17
5 / 100
 2000 ms 65540 KB 
/*
    Problem: https://oj.uz/problem/view/balkan11_timeismoney

    Solution: http://www.boi2011.ro/resurse/tasks/timeismoney-sol.pdf
*/
#include <bits/stdc++.h>
using namespace std;

#ifdef LOCAL
    #define D(a) cerr << #a << " = " << a << endl
#else 
    #define D(a) 8 
#endif
#define fastio ios_base::sync_with_stdio(0); cin.tie(0)
#define dforsn(i,s,n) for(int i=int(n-1);i>=int(s);i--)
#define forsn(i,s,n) for(int i=int(s);i<int(n);i++)
#define all(a) (a).begin(),(a).end()
#define dforn(i,n) dforsn(i,0,n)
#define forn(i,n) forsn(i,0,n)
#define si(a) int((a).size())
#define pb emplace_back
#define mp make_pair
#define snd second
#define fst first
#define endl '\n'
using pii = pair<int,int>;
using vi = vector<int>;
using ll = long long;

struct DSU {
    vi par;
    DSU(int n): par(n) { iota(all(par), 0); }
    int find(int u) { return par[u] == u ? u : par[u] = find(par[u]); }
    bool join(int u, int v) {
        if ((u = find(u) == (v = find(v)))) return false;
        return par[v] = u, true;
    }
};

const int N = 200, M = 1e4;
int n, m, A, B, sumT, sumC;
int t[M], c[M], mst[N];
int src[M], dst[M];
ll mn = 1e18;
pii ids[M];

struct Point {
    int x, y;
    bool collinear(const Point &p1, const Point &p2) {
        return ll(p2.y - p1.y) * (x - p1.x) == ll(y - p1.y) * (p2.x - p1.x);
    }
};

// Minimize a * sumT + b * sumC = v
Point optimize(int a, int b) { 
    forn(i, m) ids[i] = {a*t[i] + b*c[i], i};
    sort(ids, ids + m);
    sumT = 0, sumC = 0;
    int pos = 0;
    DSU dsu(n);
    forn(i, m) {
        int id = ids[i].snd;
        if (dsu.join(src[id], dst[id]))
            sumT += t[id], sumC += c[id], mst[pos++] = id;
    }
    ll v = ll(sumT) * sumC;
    if (v < mn) mn = v, A = a, B = b;
    return {sumC, sumT};
}

void computeConvexHull(const Point &p1, const Point &p2) {
    Point p = optimize(p2.x - p1.x, p1.y - p2.y);
    if (p.collinear(p1, p2)) return;
    computeConvexHull(p1, p), computeConvexHull(p, p2);
}

int main() {
    fastio;

    cin >> n >> m;
    forn(i, m) cin >> src[i] >> dst[i] >> t[i] >> c[i];

    computeConvexHull(optimize(0, 1), optimize(1, 0));

    optimize(A, B); 
    cout << sumT << ' ' << sumC << endl;
    forn(i, n-1) cout << src[mst[i]] << ' ' << dst[mst[i]] << endl;
    return 0;
}

Subtask #1
5.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Incorrect 0 ms 384 KB Output isn't correct
3 Incorrect 1 ms 384 KB Output isn't correct
4 Incorrect 1 ms 384 KB Output isn't correct
5 Incorrect 1 ms 384 KB Output isn't correct
6 Execution timed out 2079 ms 8816 KB Time limit exceeded
7 Execution timed out 2079 ms 1248 KB Time limit exceeded
8 Execution timed out 2082 ms 1144 KB Time limit exceeded
9 Runtime error 735 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
10 Runtime error 1496 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
11 Runtime error 1085 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
12 Execution timed out 2064 ms 45912 KB Time limit exceeded
13 Execution timed out 2079 ms 42760 KB Time limit exceeded
14 Execution timed out 2078 ms 5368 KB Time limit exceeded
15 Execution timed out 2092 ms 6016 KB Time limit exceeded
16 Execution timed out 2086 ms 1340 KB Time limit exceeded
17 Execution timed out 2089 ms 1272 KB Time limit exceeded
18 Execution timed out 2082 ms 1248 KB Time limit exceeded
19 Execution timed out 2080 ms 1144 KB Time limit exceeded
20 Execution timed out 2079 ms 1528 KB Time limit exceeded