oj.uz

Submission #237620

# Submission time Handle Problem Language Result Execution time Memory
237620 2020-06-07T21:52:25 Z VEGAnn timeismoney (balkan11_timeismoney) C++14
20 / 100
 20 ms 896 KB 
#include <bits/stdc++.h>
#define l2 array<ll,2>
using namespace std;
typedef long long ll;
typedef long double ld;
const int N = 210;
const int M = 10010;
const ll OO = 1e18;
const ld E = 1e-9;
int n, m, x[M], y[M], t[M], c[M], nm[N], pr[N], gcnt = 0, msa, msb;
ll ans = OO;
ld ga, gb, ma, mb;

ld func(int nm){
    return ld(t[nm]) * ga + ld(c[nm]) * gb;
}

bool cmp(int _x, int _y){
    return (func(_x) < func(_y));
}

bool cmp1(int _x, int _y){
    if (t[_x] == t[_y])
        return c[_x] < c[_y];
    else return t[_x] < t[_y];
}

bool cmp2(int _x, int _y){
    if (c[_x] == c[_y])
        return t[_x] < t[_y];
    else return c[_x] < c[_y];
}

int get(int x) { return (pr[x] == x ? x : pr[x] = get(pr[x])); }

l2 build(ld a, ld b, bool flag){
    ga = a; gb = b;

    if (gcnt == 0)
        sort(nm, nm + m, cmp1);
    else if (gcnt == 1)
        sort(nm, nm + m, cmp2);
    else sort(nm, nm + m, cmp);

    gcnt++;

    for (int i = 0; i < n; i++)
        pr[i] = i;

    int sa = 0, sb = 0;

    for (int it = 0; it < m; it++){
        int i = nm[it];

        int cx = get(x[i]), cy = get(y[i]);

        if (cx == cy) continue;

        if (flag)
            cout << x[i] << " " << y[i] << '\n';

        pr[cx] = cy;

        sa += t[i];
        sb += c[i];
    }

    if (ans > ll(sa) * ll(sb)){
        ans = ll(sa) * ll(sb);
        msa = sa;
        msb = sb;
        ma = ga;
        mb = gb;
    }

    return {sa, sb};
}

bool ok(l2 fi, l2 se, l2 td){
    return (se[0] - fi[0]) * (td[1] - fi[1]) - (se[1] - fi[1]) * (td[0] - fi[0]) < 0;
}

void calc(l2 lf, l2 rt){
    ld na = ld(rt[1]) - ld(lf[1]);
    ld nb = ld(lf[0]) - ld(rt[0]);

    l2 cur = build(na, nb, 0);

    if (!ok(lf, rt, cur)) return;

    calc(lf, cur);
    calc(cur, rt);
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);

#ifdef _LOCAL
    freopen("in.txt","r",stdin);
#endif // _LOCAL

    cin >> n >> m;

    for (int i = 0; i < m; i++){
        cin >> x[i] >> y[i] >> t[i] >> c[i];
        nm[i] = i;
    }

    calc(build(1.0, 0.0, 0), build(0.0, 1.0, 0));

    cout << msa << " " << msb << '\n';

    build(ma, mb, 1);

    return 0;
}

Subtask #1
20.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 6 ms 384 KB Output is correct
5 Incorrect 5 ms 384 KB Output isn't correct
6 Runtime error 5 ms 640 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Incorrect 7 ms 384 KB Output isn't correct
8 Runtime error 10 ms 896 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Incorrect 4 ms 384 KB Output isn't correct
10 Incorrect 4 ms 384 KB Output isn't correct
11 Incorrect 5 ms 384 KB Output isn't correct
12 Incorrect 5 ms 384 KB Output isn't correct
13 Incorrect 5 ms 384 KB Output isn't correct
14 Incorrect 5 ms 384 KB Output isn't correct
15 Incorrect 5 ms 384 KB Output isn't correct
16 Incorrect 7 ms 384 KB Output isn't correct
17 Incorrect 7 ms 384 KB Output isn't correct
18 Incorrect 7 ms 384 KB Output isn't correct
19 Runtime error 20 ms 896 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Runtime error 11 ms 896 KB Execution killed with signal 11 (could be triggered by violating memory limits)