oj.uz

Submission #1009921

# Submission time Handle Problem Language Result Execution time Memory
1009921 2024-06-28T08:00:46 Z vjudge1 timeismoney (balkan11_timeismoney) C++17
60 / 100
 12 ms 2456 KB 
#include <bits/stdc++.h>
using namespace std;

const int MAX = 305;
typedef unsigned long long ll;

struct Edge{
    ll a, b, x, y;
};
struct Poll{
    ll x = 0, y = 0;
    vector<Edge> v = vector<Edge>{};
};
bool eq(Poll& p1, Poll& p2){
    return p1.x == p2.x && p1.y == p2.y;
}

ll n, m, boss[MAX];
vector<Edge> edges;

ll findBoss(ll node){
    if(boss[node] == node) return node;
    return boss[node] = findBoss(boss[node]);
}

Poll solve(ll xCoeff, ll yCoeff){
    for(ll i = 0; i < MAX; i++) boss[i] = i;

    auto v = edges;
    sort(v.begin(), v.end(), [&](const Edge& e1, const Edge& e2){
         return (ll)xCoeff*e1.x + (ll)yCoeff*e1.y < (ll)xCoeff*e2.x + (ll)yCoeff*e2.y;
         });

    Poll ret;
    ret.x = 0; ret.y = 0;
    for(auto e : v){
        ll a = findBoss(e.a), b = findBoss(e.b);
        if(a == b) continue;

        if(rand() % 2) swap(a, b);
        boss[a] = b;

        ret.v.push_back(e);
        ret.x += e.x;
        ret.y += e.y;
    }

    return ret;
}

void prll(Poll& p){
    cout << p.x << ' ' << p.y << '\n';
    for(auto e : p.v) cout << e.a << ' ' << e.b << '\n';
}

Poll best;
void rek(Poll& a, Poll& b){
assert(a.x < b.x);
    Poll novi = solve(a.y - b.y, b.x - a.x);
    if(a.x * (b.y - novi.y) + b.x * (novi.y - a.y) + novi.x * (a.y - b.y) == 0) return;

    /*cout << "a\n";
    cout << a.x << ' ' << a.y << '\n';
    cout << "b\n";
    cout << b.x << ' ' << b.y << '\n';
    cout << "novi\n";
    cout << novi.x << ' ' << novi.y << '\n';*/
    if((ll)novi.x * novi.y < (ll)best.x * best.y) best = novi;

    rek(a, novi);
    rek(novi, b);
}

int main(){
    srand(time(0));

    cin >> n >> m;
    for(ll i = 0; i < m; i++){
        Edge e;
        cin >> e.a >> e.b >> e.x >> e.y;
        edges.push_back(e);
    }

    Poll minX = solve(1, 0);
    Poll minY = solve(0, 1);

    best = minX;
    if((ll)best.x * best.y < (ll)minY.x * minY.y) best = minY;

    if(!eq(minX, minY)) rek(minX, minY);

    prll(best);

    return 0;
}

Subtask #1
60.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 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 1 ms 348 KB Output is correct
7 Correct 2 ms 604 KB Output is correct
8 Correct 6 ms 984 KB Output is correct
9 Incorrect 0 ms 348 KB Output isn't correct
10 Incorrect 0 ms 344 KB Output isn't correct
11 Correct 0 ms 348 KB Output is correct
12 Runtime error 1 ms 604 KB Execution killed with signal 6
13 Correct 1 ms 348 KB Output is correct
14 Correct 5 ms 348 KB Output is correct
15 Correct 4 ms 348 KB Output is correct
16 Runtime error 3 ms 860 KB Execution killed with signal 6
17 Runtime error 3 ms 860 KB Execution killed with signal 6
18 Runtime error 3 ms 856 KB Execution killed with signal 6
19 Runtime error 12 ms 2444 KB Execution killed with signal 6
20 Runtime error 12 ms 2456 KB Execution killed with signal 6