Submission #1292657

#	Time	Username	Problem	Language	Result	Execution time	Memory
1292657		LucaDantas	timeismoney (balkan11_timeismoney)	C++17	100 / 100	290 ms	1092 KiB

timeismoney

// AI Generated code for testing if it's right, I already solved it before a few years ago but I wanted to see if AI could solve it



/*
 * Problem: Time is Money (Balkan Olympiad in Informatics 2011)
 * Method: Primal-Dual / Geometry on Convex Hull
 * Complexity: O(K * M * alpha(N)), where K is the number of hull vertices (usually small)
 */

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

// Data structures
struct Edge {
    int u, v, t, c, id;
};

struct Point {
    long long x, y; // x = sumTime, y = sumMoney
};

int N, M;
vector<Edge> edges;

// Global variables to store the best solution found so far
long long minV = -1;
Point bestPoint;
// We store the coefficients (A, B) that produced the best solution
// so we can reconstruct the tree at the end for printing.
long long bestA = 0, bestB = 0;

// Union-Find (DSU) structures
vector<int> parent;

void dsu_init(int n) {
    parent.resize(n);
    for (int i = 0; i < n; ++i) parent[i] = i;
}

int dsu_find(int i) {
    if (parent[i] == i)
        return i;
    return parent[i] = dsu_find(parent[i]);
}

void dsu_union(int i, int j) {
    int root_i = dsu_find(i);
    int root_j = dsu_find(j);
    if (root_i != root_j) {
        parent[root_i] = root_j;
    }
}

// Kruskal's Algorithm with dynamic weights A*t + B*c
// Returns the (SumTime, SumMoney) of the resulting tree
Point getMST(long long A, long long B) {
    // Sort edges based on current weights
    sort(edges.begin(), edges.end(), [A, B](const Edge& a, const Edge& b) {
        long long valA = A * a.t + B * a.c;
        long long valB = A * b.t + B * b.c;
        return valA < valB;
    });

    dsu_init(N);
    long long sumT = 0;
    long long sumC = 0;
    int edgesCount = 0;

    for (const auto& e : edges) {
        if (dsu_find(e.u) != dsu_find(e.v)) {
            dsu_union(e.u, e.v);
            sumT += e.t;
            sumC += e.c;
            edgesCount++;
        }
    }
    
    // Update global minimum if this tree is better
    long long currentV = sumT * sumC;
    if (minV == -1 || currentV < minV || (currentV == minV && sumT < bestPoint.x)) {
        minV = currentV;
        bestPoint = {sumT, sumC};
        bestA = A;
        bestB = B;
    }

    return {sumT, sumC};
}

// Recursive function to find hull points
void solve(Point p1, Point p2) {
    // Calculate weights perpendicular to the line segment p1-p2
    // We use absolute differences for positive weights
    long long A = abs(p1.y - p2.y);
    long long B = abs(p1.x - p2.x);

    // Run MST with new weights
    Point pNew = getMST(A, B);

    // Check if pNew is effectively the same as endpoints (prevents infinite loops)
    if (pNew.x == p1.x && pNew.y == p1.y) return;
    if (pNew.x == p2.x && pNew.y == p2.y) return;

    // Geometry check: Is pNew strictly "below" the segment p1-p2?
    // We check using cross product logic.
    // Vector P1->P2: (p2.x - p1.x, p2.y - p1.y)
    // Vector P1->New: (pNew.x - p1.x, pNew.y - p1.y)
    // Cross product (x1*y2 - x2*y1). If < 0, it's to the right (below/concave).
    long long cross_product = (p2.x - p1.x) * (pNew.y - p1.y) - (p2.y - p1.y) * (pNew.x - p1.x);

    // If cross_product >= 0, the point is not improving the lower hull
    if (cross_product >= 0) return;

    // Recurse
    solve(p1, pNew);
    solve(pNew, p2);
}

int main() {
    // Optimize I/O operations
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    if (fopen("timeismoney.in", "r")) {
        freopen("timeismoney.in", "r", stdin);
        freopen("timeismoney.out", "w", stdout);
    }

    cin >> N >> M;

    for (int i = 0; i < M; ++i) {
        int u, v, t, c;
        cin >> u >> v >> t >> c;
        edges.push_back({u, v, t, c, i});
    }

    // Step 1: Find extreme points
    // Minimize only Time (Weight: 1*t + 0*c)
    Point pTime = getMST(1, 0);
    
    // Minimize only Money (Weight: 0*t + 1*c)
    Point pMoney = getMST(0, 1);

    // Step 2: Start recursive search between the extremes
    solve(pTime, pMoney);

    // Step 3: Output
    cout << bestPoint.x << " " << bestPoint.y << endl;

    // To print the actual edges, we re-run the MST one last time
    // using the cached best weights to reconstruct the specific tree.
    sort(edges.begin(), edges.end(), [](const Edge& a, const Edge& b) {
        long long valA = bestA * a.t + bestB * a.c;
        long long valB = bestA * b.t + bestB * b.c;
        return valA < valB;
    });

    dsu_init(N);
    for (const auto& e : edges) {
        if (dsu_find(e.u) != dsu_find(e.v)) {
            dsu_union(e.u, e.v);
            cout << e.u << " " << e.v << endl;
        }
    }

    return 0;
}

Compilation message (stderr)

timeismoney.cpp: In function 'int main()':
timeismoney.cpp:130:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  130 |         freopen("timeismoney.in", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
timeismoney.cpp:131:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  131 |         freopen("timeismoney.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100