Submission #1214545

#TimeUsernameProblemLanguageResultExecution timeMemory
1214545nrg_studiotimeismoney (balkan11_timeismoney)C++20
50 / 100
2097 ms33112 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define pb push_back #define pii pair<int,int> #define f first #define s second #define chmin(a, b) a = min(a,b) #define chmax(a, b) a = max(a,b) #define FOR(i, a, b) for (int i = (a); i < (b); i++) #define F0R(i, a) for (int i = 0; i < (a); i++) #define all(x) x.begin(),x.end() #define vec vector const int MAX_N = 200, MAX_M = 10000; struct DSU { int par[MAX_N], sz[MAX_N]; int get(int x) {return par[x]==x ? x : par[x]=get(par[x]);} bool unite(int a, int b) { a = get(a); b = get(b); if (a==b) {return false;} if (sz[a]<sz[b]) {swap(a,b);} par[b] = a; sz[a] += sz[b]; return true; } void reset() { iota(par,par+MAX_N,0); memset(sz,1,sizeof(sz)); } }; struct Edge { int u, v, t, c; }; bool cmp1(const Edge& a, const Edge& b) {return a.t<b.t;} bool cmp2(const Edge& a, const Edge& b) {return a.c<b.c;} Edge ed[MAX_M]; DSU dsu; ll c_ans = 1e9, t_ans = 1e9, c_tot, t_tot; Edge ans[MAX_N], cand[MAX_N]; int n, m; ll scalex, scaley; bool cmp3(const Edge& a, const Edge& b) {return scalex*a.t+scaley*a.c<scalex*b.t+scaley*b.c;} void calc() { dsu.reset(); c_tot = 0, t_tot = 0; for (int i=0,ptr=0;i<m;i++) { if (dsu.unite(ed[i].u,ed[i].v)) { cand[ptr++] = ed[i]; c_tot += ed[i].c; t_tot += ed[i].t; if (ptr==n-1) {break;} } } if (c_tot*t_tot<c_ans*t_ans) { c_ans = c_tot; t_ans = t_tot; copy(cand,cand+n-1,ans); } } int main() { ios::sync_with_stdio(false); cin.tie(0); cin >> n >> m; for (int i=0;i<m;i++) {cin >> ed[i].u >> ed[i].v >> ed[i].t >> ed[i].c;} stack<pair<pii,pii>> todo; sort(ed,ed+m,cmp1); calc(); pii a0 = {t_tot,c_tot}; //ll ax = t_tot, ay = c_tot; sort(ed,ed+m,cmp2); calc(); pii b0 = {t_tot,c_tot}; //ll bx = t_tot, by = c_tot; //cout << ax<<' ' <<ay<<' '<<bx<<' '<<by<<'\n'; //solve(ax,ay,bx,by); todo.push({a0,b0}); while (todo.size()) { auto[a,b] = todo.top(); todo.pop(); scalex = a.s-b.s; scaley = b.f-a.f; sort(ed,ed+m,cmp3); calc(); pii c = {t_tot,c_tot}; if ((ll)(b.f-a.f)*(c.s-a.s)-(ll)(b.s-a.s)*(c.f-a.f)<=0 && c!=a && c!=b) { todo.push({a,c}); todo.push({c,b}); } } cout << t_ans << ' ' << c_ans << '\n'; for (int i=0;i<n-1;i++) {cout << ans[i].u << ' ' << ans[i].v << '\n';} }
#Verdict Execution timeMemoryGrader output
Fetching results...