oj.uz

답안 #392619

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
392619 2021-04-21T11:16:09 Z Vladth11 시간이 돈 (balkan11_timeismoney) C++14
100 / 100
 1247 ms 976 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define debug(x) cerr << #x << " " << x << "\n"
#define debug_with_space(x) cerr << #x << " " << x << " "

using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef pair <ll, ll> pii;
typedef pair <long double, pii> muchie;
typedef tree <ll, null_type, less_equal <ll>, rb_tree_tag, tree_order_statistics_node_update> OST;

const ll NMAX = 501;
const ll INF = (1LL << 60);
const ll MOD = 666013;
const ll BLOCK = 225;
const ll base = 31;
const ll nr_of_bits = 8;

ll n;

struct edge {
    ll x, y, t, c;
};

ll parent[NMAX], cnt[NMAX];
ll root(ll x) {
    if(x == parent[x]) {
        return x;
    }
    return parent[x] = root(parent[x]);
}
ll cost, timp;
vector <edge> fol;
void init(ll n) {
    cost = timp = 0;
    fol.clear();
    for(ll i = 1; i <= n; i++) {
        parent[i] = i;
        cnt[i] = 1;
    }
}
void merge(edge x) {
    ll a = root(x.x);
    ll b = root(x.y);
    if(a == b)
        return;
    if(cnt[a] < cnt[b])
        swap(a, b);
    cnt[a] += cnt[b];
    cnt[b] = 0;
    parent[b] = a;
    cost += x.c;
    timp += x.t;
    fol.push_back(x);
}


ll dx, dy;
pii best;
ll minim = (1LL << 60);
ll _prll;

bool cmp(edge a, edge b) {
    return a.t * dx + a.c * dy < b.t * dx + b.c * dy;
}

vector <edge> edges;

ll OK(pii a, pii b, pii c) {
    return (a.first * (b.second - c.second) + b.first * (c.second - a.second) + c.first * (a.second - b.second) == 0);
}

pii MST() {
    sort(edges.begin(), edges.end(), cmp);
    init(n);
    for(auto x : edges) {
        merge(x);
    }
    if(cost * timp < minim) {
        minim = cost * timp;
        best = {dx, dy};
    }
    if(!_prll)
        return {cost, timp};

    cout << timp << " " << cost << "\n";
    for(auto x : fol) {
        cout << x.x - 1 << " " << x.y - 1 << "\n";
    }
  return {cost, timp};
}

void Solve(pii A, pii B) {
    dx = B.first - A.first;
    dy = A.second - B.second;
    pii C = MST();
    // debug(C.first);
    // debug(C.second);
    if(OK(A, C, B)) {
        return;
    }

    Solve(A, C);
    Solve(C, B);
}

int main() {
    //ifstream cin("grarbore.in");
    //ofstream cout("grarbore.out");
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    ll m;
    cin >> n >> m;
    for(ll i = 1; i <= m; i++) {
        edge x;
        cin >> x.x >> x.y >> x.t >> x.c;
        x.x++;
        x.y++;
        edges.push_back(x);
    }
    dx = 0;
    dy = 1;
    pii A = MST();
    dx = 1;
    dy = 0;
    pii B = MST();
    Solve(A, B);
    _prll = 1;
    dx = best.first;
    dy = best.second;
    MST();
    return 0;
}

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 3 ms 332 KB Output is correct
8 Correct 8 ms 976 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 8 ms 332 KB Output is correct
15 Correct 5 ms 332 KB Output is correct
16 Correct 134 ms 432 KB Output is correct
17 Correct 142 ms 436 KB Output is correct
18 Correct 147 ms 428 KB Output is correct
19 Correct 1243 ms 976 KB Output is correct
20 Correct 1247 ms 976 KB Output is correct