Submission #1269902

#	Time	Username	Problem	Language	Result	Execution time	Memory
1269902		golions	timeismoney (balkan11_timeismoney)	C++17	100 / 100	332 ms	584 KiB

timeismoney

#include <bits/stdc++.h>
//http://www.boi2011.ro/resurse/tasks/timeismoney-sol.pdf
//https://www.cnblogs.com/TenderRun/p/5700737.html
using namespace std;

typedef pair<long long, long long> pll;

struct Edge{
   int x;
   int y;
   long long a;
   long long b;
   
   long long val(long long la, long long lb) const {
      return la*a + lb*b;
   }
};

int n,m;
vector<Edge> edges;

long long ans1 = 1000000LL;
long long ans2 = 1000000LL;
vector<Edge> ea;

//dsu
vector<int> parent;

int getpar(int v){
   if(parent[v] == v) return v;
   parent[v] = getpar(parent[v]);
   return parent[v];
}

void join(int u, int v){
   int pu = getpar(u);
   int pv = getpar(v);
   
   parent[pu] = pv;
}


pll solve(long long la,long long lb){
   //cout << la << " " << lb << endl;
   sort(edges.begin(),edges.end(),[&](const Edge& e1, const Edge& e2){return e1.val(la,lb) < e2.val(la,lb);});
   
   vector<Edge> cur;
   
   for(int k = 0; k < n; k++){
      parent[k] = k;
   }
   
   long long a1 = 0LL;
   long long a2 = 0LL;
   for(int k = 0; k < m; k++){
      if(getpar(edges[k].x) != getpar(edges[k].y)){
         join(edges[k].x,edges[k].y);
         cur.push_back(edges[k]);
         a1 += edges[k].a;
         a2 += edges[k].b;
      }
   }
   
   long long curanswer = a1*a2;
   if(curanswer < ans1*ans2){
      ans1 = a1;
      ans2 = a2;
      ea = cur;
   }
   return make_pair(a1,a2);
}

//>0 is ccw, <0 is cw, 0 is on the line
long long cross_productz(pll a, pll b, pll c){
   return (b.first-a.first) * (c.second-b.second) - (c.first-b.first) * (b.second-a.second);
}

void dothing(pll pl, pll pr){
   auto mid = solve(pl.second-pr.second,pr.first-pl.first);
   
   //skip if mid is on the line between pl and pr
   if(cross_productz(pl,pr,mid) >= 0){
      //should never be > 0, but could be =0
      return;
   }
   
   dothing(pl,mid);
   dothing(mid,pr);
}


int main(){
   ios::sync_with_stdio(false);
   cin.tie(0);
   
   cin >> n >> m;
   
   edges = vector<Edge>(m);
   for(int k = 0; k < m; k++){
      int x,y;
      long long a,b;
      cin >> x >> y >> a >> b;
      
      edges[k] = {x,y,a,b};
   }
   
   parent = vector<int>(n);
   
   auto p1 = solve(1LL,0LL);
   auto p2 = solve(0LL,1LL);
   
   dothing(p1,p2);
   
   cout << ans1 << " " << ans2 << "\n";
   for(int k = 0; k < n-1; k++){
      cout << ea[k].x << " " << ea[k].y << "\n";
   }
   
   return 0;
}

• Subtask 1: 100 / 100