oj.uz

답안 #392607

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
392607 2021-04-21T11:06:26 Z Vladth11 시간이 돈 (balkan11_timeismoney) C++14
15 / 100
 10 ms 1104 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, B, C)) {
        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
15.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Incorrect 1 ms 332 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 2 ms 464 KB Output isn't correct
8 Incorrect 9 ms 1104 KB Output isn't correct
9 Incorrect 1 ms 204 KB Output isn't correct
10 Incorrect 1 ms 332 KB Output isn't correct
11 Incorrect 1 ms 204 KB Output isn't correct
12 Incorrect 1 ms 204 KB Output isn't correct
13 Incorrect 1 ms 332 KB Output isn't correct
14 Incorrect 1 ms 332 KB Output isn't correct
15 Incorrect 1 ms 332 KB Output isn't correct
16 Incorrect 2 ms 460 KB Output isn't correct
17 Incorrect 3 ms 460 KB Output isn't correct
18 Incorrect 2 ms 460 KB Output isn't correct
19 Incorrect 10 ms 1104 KB Output isn't correct
20 Incorrect 10 ms 1104 KB Output isn't correct