제출 #1188990

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1188990		fadak-14	시간이 돈 (balkan11_timeismoney)	C++20	45 / 100	41 ms	840 KiB

timeismoney

//Wa of course, please give me ac !!! im begging u compiler-sama, have mercy on my poor code !
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define db double
#define ld long double
#define endl '\n'
#define eb emplace_back
#define em emplace
#define pb push_back
#define pf push_front
#define pp pop_back
#define fr first
#define sc second
#define sz size
const ll mm = 10010;
const ll mx = 205 ;
ll p[mx];
ll f(ll x) {
    return p[x] == x ? x : p[x] = f(p[x]);
}
bool un(ll a , ll b) {
    ll ra = f(a) , rb = f(b) ;
    if(ra == rb) return false ;
    p[rb] = ra ;
    return true ;
}
ll n , m ;
array<ll , 5> ed[mm] ;
ll bv = 1e18 ,bt , bc;
vector<pair<ll , ll>> be;
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0) ; cout.tie(0);
     cin >> n >> m;
    for(ll i = 0 ; i < m ; i++) {
        cin >> ed[i][3] >> ed[i][4] >> ed[i][1] >> ed[i][2] ;
        ed[i][0] = ed[i][1] *ed[i][2];
    }
    sort(ed , ed + m);
    for(ll i = 0 ; i < m ;i++){

    }
    for (ll i = 0; i < m; i++) {
        for(ll j = 0 ; j < n ;j++) p[j] = j ;
        ll cnt = 0 , ts = 0 , cs = 0;
        vector <pair<ll , ll>> ch ;
        for(ll j = i ; j <m ;j++) {
            ll u = ed[j][3], v = ed[j][4];
            ll t = ed[j][1], c = ed[j][2];
            if(un(u ,v)){
                ts += t;
                cs += c ;
                ch.eb(u , v) ;
                cnt++ ;
                if(cnt == n -1) break ;
            }
        }
        if(cnt == n - 1) {
            ll vl = ts * cs ;
            if(vl < bv) {
                bv = vl ;
                bt = ts ;
                bc = cs ;
                be = ch ; 
            }
        }
    }
    cout << bt <<" " << bc << endl;
    for(auto [u, v] : be) cout << u << " " << v << endl;
    return 0 ;
}
  

• Subtask 1: 45 / 100