Submission #1009693

#TimeUsernameProblemLanguageResultExecution timeMemory
1009693vjudge1timeismoney (balkan11_timeismoney)C++17
100 / 100
750 ms768 KiB
#include <bits/stdc++.h> #define ll long long #define pb push_back #define mp make_pair #define F first #define S second #define pii pair < ll, ll > #define FIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); using namespace std; struct Edge { ll a, b, t, m; }; const ll N = 2e2+10, M = 1e4+10; ll n, m; Edge edges[M]; ll x, y; ll par[N]; ll sz[N]; vector < pii > konfig; ll msol = 1e18+7; vector < pii > solkonfig; int fn( int i ) { if(par[i] == i) return i; return par[i] = fn(par[i]); } void un( int a, int b ) { a = fn(a); b = fn(b); if(a != b) { if(sz[a] > sz[b]) swap(a, b); par[a] = b; sz[a] += sz[b]; } return; } void res( void ) { for(ll i = 0; i < n; i++) { par[i] = i; sz[i] = 1; } konfig.clear(); } bool check_un( int a, int b ) { return (fn(a) == fn(b)); } pii mst() { ll tout = 0; ll mout = 0; res(); int tot = 0; for(ll i = 0; i < m; i++) { if(!check_un(edges[i].a, edges[i].b)) { un(edges[i].a, edges[i].b); tout += edges[i].t; mout += edges[i].m; tot++; konfig.pb(mp(edges[i].a, edges[i].b)); } } if(tout*mout < msol) { msol = tout*mout; solkonfig = konfig; } return mp(tout, mout); } bool s_func_t( Edge a, Edge b ) { if(b.t > a.t) return 1; if(b.t < a.t) return 0; if(b.m > a.m) return 1; return 0; } bool s_func_m( Edge a, Edge b ) { if(b.m > a.m) return 1; if(b.m < a.m) return 0; if(b.t > a.t) return 1; return 0; } bool s_func_xy( Edge a, Edge b ) { return ((b.t * x) + (b.m * y) > (a.t * x) + (a.m * y)) ? 1 : 0; } inline pii daq( pii a, pii b ) { y = b.F - a.F; x = a.S - b.S; sort(edges, edges + m, s_func_xy); pii temp1; pii temp2; pii out = mst(); if(out.F*x+out.S*y == a.F*x+a.S*y || out.F*x+out.S*y == b.F*x+b.S*y) { if(a.F * a.S < b.F * b.S) return a; else return b; } temp1 = daq(a, out); temp2 = daq(out, b); if(temp1.F * temp1.S < out.F * out.S) out = temp1; if(temp2.F * temp2.S < out.F * out.S) out = temp2; return out; } int main( void ) { FIO cin >> n >> m; for(int i = 0; i < m; i++) { cin >> edges[i].a >> edges[i].b >> edges[i].t >> edges[i].m; } sort(edges, edges + m, s_func_t); pii temp1 = mst(); sort(edges, edges + m, s_func_m); pii temp2 = mst(); pii sol = daq(temp1, temp2); cout << sol.F << " " << sol.S << "\n"; for(int i = 0; i < (int) solkonfig.size(); i++) { cout << solkonfig[i].F << " " << solkonfig[i].S << "\n"; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...