oj.uz

Submission #1010542

# Submission time Handle Problem Language Result Execution time Memory
1010542 2024-06-29T07:56:55 Z vjudge1 timeismoney (balkan11_timeismoney) C++17
50 / 100
 2000 ms 65536 KB 
// ^^
// <{:3
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,popcnt,tune=native")
//#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
#pragma GCC optimize("O3")
#include<bits/stdc++.h>
//#define int long signed long int
#define ld long double
using namespace std;
const int maxn = 202;
vector<tuple<ld, ld, int, int>> edges; // c t x y
pair<int, ld> ans; // val, k
int p[maxn];
int n, m;

inline void rt() { for(int i = 0; i <= n; ++i) p[i] = i; }

int f(int x)
{
    if(p[x] == x) return x;
    return p[x] = f(p[x]);
}

inline void u(int x, int y)
{
    x = f(x); y = f(y);
    if(x == y) return;
    p[x] = y;
}

pair<int, int> mst(ld k)
{
    vector<tuple<ld, ld, ld, int, int>> v;
    rt();

    for(auto [c, t, x, y] : edges) v.emplace_back(t+k*c, c, t, x, y);
    sort(v.begin(), v.end());

    pair<int, int> ret(0, 0);
    for(auto [val, c, t, x, y] : v)
    {
        if(f(x) != f(y))
        {
            ret.first += c;
            ret.second += t;
            u(x, y);
        }
    }

    return ret;
}

void rec(ld x1, ld y1, ld x2, ld y2)
{
    if(x1 == x2) return;

    ld k = (y1 - y2) / (x1 - x2);
    ld c = y1 - (k * x1);

    pair<int, int> novi = mst(-k);

    ld y = (k*novi.first) + c;

    //cout << novi.first << " " << novi.second << " " << k << " dbdb\n";

    if(novi.second >= y) return;

    if(novi.first * novi.second < ans.first)
    {
        ans.first = novi.first * novi.second;
        ans.second = k;
    }

    rec(x1, y1, novi.first, novi.second);
    rec(x2, y2, novi.first, novi.second);
}

signed main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    ans = {1e9, 0};

    cin >> n >> m;

    for(int i = 0; i < m; ++i)
    {
        ld t, c;
        int x, y;
        cin >> x >> y >> t >> c;
        edges.emplace_back(t, c, x, y);
    }

    rt();
    vector<pair<int, int>> minte, mince;
    sort(edges.begin(), edges.end());
    pair<int, int> mint(0, 0);
    for(auto &[t, c, x, y] : edges)
    {
        int xtr = f(x), ytr = f(y);
        if(xtr != ytr)
        {
            mint.first += c;
            mint.second += t;
            minte.emplace_back(x, y);
            u(xtr, ytr);
        }
        swap(t, c);
    }

    rt();
    sort(edges.begin(), edges.end());
    pair<int, int> minc(0, 0);
    for(auto &[c, t, x, y] : edges)
    {
        int xtr = f(x), ytr = f(y);
        if(xtr != ytr)
        {
            minc.first += c;
            minc.second += t;
            mince.emplace_back(x, y);
            u(xtr, ytr);
        }
    }

    rec(minc.first, minc.second, mint.first, mint.second);

    if(minc.first * minc.second < ans.first)
    {
        swap(minc.first, minc.second);
        cout << minc.first << " " << minc.second << "\n";
        for(auto [x, y] : mince) cout << x << " " << y << "\n";
        return 0;
    }
    if(mint.first * mint.second < ans.first)
    {
        swap(mint.first, mint.second);
        cout << mint.first << " " << mint.second << "\n";
        for(auto [x, y] : minte) cout << x << " " << y << "\n";
        return 0;
    }


    rt();
    ld k = -ans.second;
    vector<tuple<ld, ld, ld, int, int>> v;
    for(auto [c, t, x, y] : edges) v.emplace_back(t+k*c, c, t, x, y);

    sort(v.begin(), v.end());

    pair<int, int> ret(0, 0);
    vector<pair<int, int>> ansedge;
    for(auto [val, c, t, x, y] : v)
    {
        if(f(x) != f(y))
        {
            ret.first += c;
            ret.second += t;
            u(x, y);
            ansedge.emplace_back(x, y);
        }
    }

    swap(ret.first, ret.second);
    cout << ret.first << " " << ret.second << "\n";
    for(auto [x, y] : ansedge) cout << x << " " << y << "\n";
}

Subtask #1
50.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 648 KB Output is correct
8 Correct 5 ms 1368 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Runtime error 1770 ms 65536 KB Execution killed with signal 9
11 Correct 0 ms 344 KB Output is correct
12 Execution timed out 2079 ms 47176 KB Time limit exceeded
13 Execution timed out 2040 ms 44024 KB Time limit exceeded
14 Execution timed out 2070 ms 8532 KB Time limit exceeded
15 Execution timed out 2064 ms 9568 KB Time limit exceeded
16 Execution timed out 2013 ms 2172 KB Time limit exceeded
17 Execution timed out 2059 ms 2248 KB Time limit exceeded
18 Execution timed out 2070 ms 2224 KB Time limit exceeded
19 Execution timed out 2102 ms 3088 KB Time limit exceeded
20 Execution timed out 2061 ms 2796 KB Time limit exceeded