oj.uz

답안 #1009355

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1009355 2024-06-27T11:57:22 Z vjudge1 시간이 돈 (balkan11_timeismoney) C++17
90 / 100
 712 ms 900 KB 
#include <bits/stdc++.h>

using namespace std;

const int MAX = 205;
typedef long long ll;

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

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

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

Point solve(int xCoeff, int yCoeff){
    for(int 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;
         });

    Point ret;
    ret.x = 0; ret.y = 0;
    for(auto e : v){
        int 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 print(Point& p){
    cout << p.x << ' ' << p.y << '\n';
    for(auto e : p.v) cout << e.a << ' ' << e.b << '\n';
}

Point best;
void rek(Point& a, Point& b){
    Point 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(int i = 0; i < m; i++){
        Edge e;
        cin >> e.a >> e.b >> e.x >> e.y;
        edges.push_back(e);
    }

    Point minX = solve(1, 0);
    Point 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);

    print(best);

    return 0;
}

Subtask #1
90.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 344 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 348 KB Output is correct
8 Correct 6 ms 724 KB Output is correct
9 Incorrect 0 ms 344 KB Output isn't correct
10 Incorrect 1 ms 388 KB Output isn't correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 5 ms 348 KB Output is correct
15 Correct 3 ms 348 KB Output is correct
16 Correct 85 ms 552 KB Output is correct
17 Correct 98 ms 344 KB Output is correct
18 Correct 102 ms 552 KB Output is correct
19 Correct 690 ms 824 KB Output is correct
20 Correct 712 ms 900 KB Output is correct