Submission #392579

#	Time	Username	Problem	Language	Result	Execution time	Memory
392579		Vladth11	timeismoney (balkan11_timeismoney)	C++14	65 / 100	749 ms	716 KiB

timeismoney

#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;
 
int n;
 
struct edge {
    int x, y, t, c;
};
 
int parent[NMAX], cnt[NMAX];
int root(int x) {
    if(x == parent[x]) {
        return x;
    }
    return parent[x] = root(parent[x]);
}
int cost, timp;
vector <edge> fol;
void init(int n) {
    cost = timp = 0;
    fol.clear();
    for(int i = 1; i <= n; i++) {
        parent[i] = i;
        cnt[i] = 1;
    }
}
void merge(edge x) {
    int a = root(x.x);
    int 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);
}
 
 
int dx, dy;
pii best;
int minim = 2e9;
int _print;
 
bool cmp(edge a, edge b) {
    return 1LL * a.t * dx + 1LL * a.c * dy < 1LL * b.t * dx + 1LL * b.c * dy;
}
 
vector <edge> edges;
 
int 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(!_print)
        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);
    int m;
    cin >> n >> m;
    for(int 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);
    _print = 1;
    dx = best.first;
    dy = best.second;
    MST();
    return 0;
}

• Subtask 1: 65 / 100