Submission #392552

#	Time	Username	Problem	Language	Result	Execution time	Memory
392552		Vladth11	timeismoney (balkan11_timeismoney)	C++14	0 / 100	756 ms	1128 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 = 201;
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;
};

class DSU{
    vector <int> parent, cnt;
    int root(int x){
        if(x == parent[x]){
            return x;
        }
        return parent[x] = root(parent[x]);
    }
public:
    int cost, timp;
    vector <edge> fol;
    DSU(int n){
        cost = timp = 0;
        parent.resize(n + 1);
        fol.clear();
        cnt.resize(n + 1, 0);
        for(int i = 1; i <= n; i++){
            parent[i] = i;
        }
    }
    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 a.t * dx + a.c * dy < b.t * dx + 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);
    DSU dsu(n);
    for(auto x : edges){
        dsu.merge(x);
    }
    if(!_print)
        return {dsu.cost, dsu.timp};
    cout << dsu.timp << " " << dsu.cost << "\n";
    for(auto x : dsu.fol){
        cout << x.x << " " << x.y << "\n";
    }
}

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;
}

Compilation message (stderr)

timeismoney.cpp: In function 'pii MST()':
timeismoney.cpp:80:14: warning: control reaches end of non-void function [-Wreturn-type]
   80 |     DSU dsu(n);
      |              ^

• Subtask 1: 0 / 100