Submission #402575

#	Time	Username	Problem	Language	Result	Execution time	Memory
402575		SirCovidThe19th	timeismoney (balkan11_timeismoney)	C++14	50 / 100	95 ms	460 KiB

timeismoney

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

#define ll long long
#define ld long double

struct store{
    int x, y, t, c;
};

int n, m;
vector<store> edges;

ll currVal; int ansT, ansC; vector<pair<int, int>> links;

vector<int> par, sz; 
int find(int node){
    if (node == par[node]) return node;
    return par[node] = find(par[node]);
}
void merge(int a, int b){
    a = find(a), b = find(b);
    if (sz[a] > sz[b]) swap(a, b);
    par[a] = b; sz[b] += sz[a];
}

bool cmp1(store a, store b){
    return a.t-((long double)currVal/a.c) < b.t-((long double)currVal/b.c);
}
bool cmp2(store a, store b){
    return a.c-((long double)currVal/a.t) < b.c-((long double)currVal/b.t);
}
bool check(int whichCmp){
    if (whichCmp == 1) sort(edges.begin(), edges.end(), cmp1);
    else sort(edges.begin(), edges.end(), cmp2);
    par.resize(n); sz.resize(n, 1); iota(par.begin(), par.end(), 0);
    for (int i = 0; i < n; i++) par[i] = i;
    ansT = 0, ansC = 0, links.clear();

    for (store edge : edges){
        if (find(edge.x) != find(edge.y)){
            merge(edge.x, edge.y);
            ansT += edge.t, ansC += edge.c; links.push_back({edge.x, edge.y});
        }
    }

    return (ll)ansT*(ll)ansC <= currVal;
}
int main(){
    
    cin >> n >> m; edges.resize(m);
    for (int i = 0; i < m; i++)
        cin >> edges[i].x >> edges[i].y >> edges[i].t >> edges[i].c;

    ll low = 0; ll high = ((ll)255*n*255*n)+1;
    while (low < high){
        currVal = (low+high+1)/2;
        if (check(1) or check(2)){
            high = currVal-1;
        }
        else low = currVal;
    }
    
    cout<<ansT<<" "<<ansC<<endl;
    for (pair<int, int> elem : links) 
        cout<<elem.first<<" "<<elem.second<<endl;
}

• Subtask 1: 50 / 100