oj.uz

답안 #392581

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
392581 2021-04-21T10:47:39 Z Vladth11 시간이 돈 (balkan11_timeismoney) C++14
65 / 100
 1243 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(!_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;
    }
    if(C.first * C.second < minim) {
        minim = C.first * C.second;
        best = {dx, dy};
    }
    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
65.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 Incorrect 1 ms 204 KB Output isn't correct
5 Incorrect 1 ms 332 KB Output isn't correct
6 Incorrect 1 ms 332 KB Output isn't correct
7 Incorrect 3 ms 332 KB Output isn't correct
8 Incorrect 9 ms 976 KB Output isn't correct
9 Incorrect 1 ms 204 KB Output isn't correct
10 Incorrect 1 ms 204 KB Output isn't 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 133 ms 332 KB Output is correct
17 Correct 143 ms 444 KB Output is correct
18 Correct 137 ms 428 KB Output is correct
19 Correct 1209 ms 976 KB Output is correct
20 Correct 1243 ms 976 KB Output is correct