Submission #42435

#	Time	Username	Problem	Language	Result	Execution time	Memory
42435		choikiwon	timeismoney (balkan11_timeismoney)	C++14	100 / 100	843 ms	876 KiB

timeismoney

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

ll cross(pii a, pii b) {
    return 1LL * a.first * b.second - a.second * b.first;
}
ll ccw(pii a, pii b, pii c) {
    pii p = pii(b.first - a.first, b.second - a.second);
    pii q = pii(c.first - a.first, c.second - a.second);
    return cross(p, q);
}

int N, M, T, C;
struct Edge {
    int u, v, t, c;
};
Edge edge[10010];
vector<pii> sol, tmp;

bool cmp(Edge a, Edge b) {
    return 1LL * T * a.t + 1LL * C * a.c < 1LL * T * b.t + 1LL * C * b.c;
}

struct DSU {
    int par[202], rnk[202];
    void init() {
        for(int i = 0; i < N; i++) {
            par[i] = i;
            rnk[i] = 0;
        }
    }
    int f(int u) {
        if(par[u] == u) return u;
        else return par[u] = f(par[u]);
    }
    void mrg(int u, int v) {
        u = f(u);
        v = f(v);
        if(u == v) return;
        if(rnk[u] < rnk[v]) swap(u, v);
        par[v] = u;
        if(rnk[u] == rnk[v]) rnk[u]++;
    }
} dsu;

pii solve(int a, int b) {
    T = a;
    C = b;
    sort(edge, edge + M, cmp);

    pii ret = pii(0, 0);

    dsu.init();
    tmp.clear();
    for(int i = 0; i < M; i++) {
        int u = edge[i].u;
        int v = edge[i].v;
        int t = edge[i].t;
        int c = edge[i].c;
        if(dsu.f(u) == dsu.f(v)) continue;
        dsu.mrg(u, v);
        ret.first += t;
        ret.second += c;

        tmp.push_back(pii(u, v));
    }
    return ret;
}

pii ans = pii(1e9, 1e9);

void rec(pii s, pii e) {
    int a = e.first - s.first;
    int b = s.second - e.second;
    pii m = solve(b, a);

    if(ccw(s, m, e) > 0) {
        if(1LL * ans.first * ans.second > 1LL * m.first * m.second) {
            ans = m;
            sol = tmp;
        }
        rec(s, m);
        rec(m, e);
    }
}

int main() {
    scanf("%d %d", &N, &M);

    for(int i = 0; i < M; i++) {
        int u, v, t, c; scanf("%d %d %d %d", &u, &v, &t, &c);
        edge[i] = {u, v, t, c};
    }

    pii s = solve(1, 0);
    if(1LL * ans.first * ans.second > 1LL * s.first * s.second) {
        ans = s;
        sol = tmp;
    }

    pii e = solve(0, 1);
    if(1LL * ans.first * ans.second > 1LL * e.first * e.second) {
        ans = e;
        sol = tmp;
    }

    rec(s, e);

    printf("%d %d\n", ans.first, ans.second);
    for(int i = 0; i < sol.size(); i++) {
        printf("%d %d\n", sol[i].first, sol[i].second);
    }
}

Compilation message (stderr)

timeismoney.cpp: In function 'int main()':
timeismoney.cpp:113:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < sol.size(); i++) {
                      ^
timeismoney.cpp:91:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &N, &M);
                           ^
timeismoney.cpp:94:61: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         int u, v, t, c; scanf("%d %d %d %d", &u, &v, &t, &c);
                                                             ^

• Subtask 1: 100 / 100