oj.uz

답안 #1009966

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1009966 2024-06-28T08:22:20 Z vjudge1 시간이 돈 (balkan11_timeismoney) C++17
40 / 100
 2000 ms 1388 KB 
#include <bits/stdc++.h>

using namespace std;

const int MAX = 205;
typedef 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 < n; 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){
    Poll novi = solve(a.y - b.y, b.x - a.x);
    if(eq(a, novi) || eq(b, novi)) 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(minY, minX);

    prll(best);

    return 0;
}

Subtask #1
40.0 / 100.0

# 결과 실행 시간 메모리 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 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 628 KB Output is correct
8 Correct 6 ms 1100 KB Output is correct
9 Incorrect 0 ms 344 KB Output isn't correct
10 Incorrect 0 ms 348 KB Output isn't correct
11 Incorrect 1 ms 344 KB Output isn't correct
12 Incorrect 1 ms 348 KB Output isn't correct
13 Incorrect 1 ms 348 KB Output isn't correct
14 Incorrect 16 ms 532 KB Output isn't correct
15 Incorrect 10 ms 348 KB Output isn't correct
16 Incorrect 284 ms 692 KB Output isn't correct
17 Incorrect 277 ms 672 KB Output isn't correct
18 Incorrect 282 ms 600 KB Output isn't correct
19 Execution timed out 2056 ms 1176 KB Time limit exceeded
20 Incorrect 1989 ms 1388 KB Output isn't correct