Submission #98120

#	Time	Username	Problem	Language	Result	Execution time	Memory
98120		dalgerok	timeismoney (balkan11_timeismoney)	C++17	100 / 100	1165 ms	1276 KiB

timeismoney

#include<bits/stdc++.h>
using namespace std;


const int N = 2005;
const long long INF = 1e18;
const double eps = 1e-9;


int n, m;


bool used[N];
int p[N], pt[N], pc[N];
double d[N];
long long ans = 9e18, ans1, ans2;
vector < pair < int, int > > anss;

vector < pair < int, pair < int, int > > > g[N];
vector < pair < pair < int, int >, pair < int, int > > > e, cur_e;

inline void build(double x){
    for(int i = 1; i <= n; i++){
        d[i] = INF;
        p[i] = -1;
        used[i] = false;
    }
    d[1] = 0;
    set < pair < double, int > > q;
    q.insert(make_pair(0, 1));
    cur_e.clear();
    vector < pair < int, int > > s;
    long long cur1 = 0, cur2 = 0;
    for(int i = 1; i <= n; i++){
        int v = q.begin()->second;
        q.erase(q.begin());
        used[v] = true;
        if(p[v] != -1){
            cur_e.push_back(make_pair(make_pair(v, p[v]), make_pair(pt[v], pc[v])));
            cur_e.push_back(make_pair(make_pair(p[v], v), make_pair(pt[v], pc[v])));
            ///cout << "KEK: " << v << " " << p[v] << " " << d[v] << " " << d[p[v]] << " " << pt[v] << " " << pc[v] << "\n";
            cur1 += pt[v];
            cur2 += pc[v];
            s.push_back(make_pair(v, p[v]));
        }
        for(auto it : g[v]){
            int to = it.first,
                t = it.second.first,
                c = it.second.second;
            double val = t * x + c * (1 - x);
            if(!used[to] && d[to] > val){
                q.erase(make_pair(d[to], to));
                d[to] = val;
                p[to] = v;
                pt[to] = t;
                pc[to] = c;
                q.insert(make_pair(d[to], to));
            }
        }
    }
    ///cout << "VALS: " << cur1 << " " << cur2 << "\n";
    if(1LL * cur1 * cur2 < ans){
        ans = 1LL * cur1 * cur2;
        ans1 = cur1;
        ans2 = cur2;
        anss = s;
    }
}

int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin >> n >> m;
    for(int i = 1; i <= m; i++){
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        a += 1;
        b += 1;
        g[a].push_back(make_pair(b, make_pair(c, d)));
        g[b].push_back(make_pair(a, make_pair(c, d)));
        e.push_back(make_pair(make_pair(a, b), make_pair(c, d)));
        e.push_back(make_pair(make_pair(b, a), make_pair(c, d)));
    }
    double x = 0;
    while(true){
        double new_x = 1;
        build(x);
        for(auto it1 : cur_e){
            for(auto it2 : g[it1.first.first]){
                int t1 = it1.second.first, c1 = it1.second.second,
                    t2 = it2.second.first, c2 = it2.second.second;
                double xx = (c2 - c1) / (double)(t1 - c1 - t2 + c2);
                if(x < xx && xx <= new_x){
                    new_x = xx;
                }
            }
            for(auto it2 : g[it1.first.second]){
                int t1 = it1.second.first, c1 = it1.second.second,
                    t2 = it2.second.first, c2 = it2.second.second;
                double xx = (c2 - c1) / (double)(t1 - c1 - t2 + c2);
                if(x < xx && xx <= new_x){
                    new_x = xx;
                }
            }
        }
        if(x == new_x){
            break;
        }
        x = new_x;
    }
    cout << ans1 << " " << ans2 << "\n";
    for(auto it : anss){
        cout << it.first - 1 << " " << it.second - 1 << "\n";
    }
}

• Subtask 1: 100 / 100