Submission #373680

#	Time	Username	Problem	Language	Result	Execution time	Memory
373680		NaimSS	timeismoney (balkan11_timeismoney)	C++14	100 / 100	739 ms	620 KiB

timeismoney

#include <bits/stdc++.h>
#define ff first
#define ss second
#define rep(i,a,b) for(int i=(a);i<(b);i++)
using namespace std;
typedef long long ll;
const int N = 205;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
pii e[10100];
pii cost[10100];
const int inf = 1e9;
pll ptRes = pll(inf,inf);
int n,m;
int res[N];
int used[N];
int pai[N],sz[N];
int f(int x){
  return pai[x] = (pai[x] == x ? x : f(pai[x]));
}
int join(int a,int b){
  a=f(a),b=f(b);
  if(a==b)return 0;
  if(sz[a] > sz[b])swap(a,b);
  pai[a]=b;
  sz[b]+=sz[a];
  return 1;
}

int ids[10100];

pll kruska(pll cur){
  rep(i,0,N){
    pai[i]=i,sz[i]=1;
  }
  sort(ids,ids+m,[&](int a,int b){
    return 1ll*cur.ss * (cost[a].ff - cost[b].ff) + 1ll*cur.ff * (cost[a].ss - cost[b].ss) < 0;
  });

  int ptr=0;
  pll c = pll(0,0);
  rep(it,0,m){
    int i = ids[it];
    if(join(e[i].ff,e[i].ss)){
      used[ptr++] = i;
      c.ff+=cost[i].ff;
      c.ss+=cost[i].ss;
    }
  }
  if(c.ff * c.ss < ptRes.ff * ptRes.ss){
    ptRes = c;
    rep(i,0,n-1)res[i] = used[i];
  }
  return c;
}
int iter=0;
void go(pll A,pll B){
  if(A==B)return;
  pll C = kruska(pll(B.ff - A.ff,A.ss - B.ss));
  if((B.ff - A.ff) * (C.ss - A.ss) - (B.ss - A.ss) * (C.ff - A.ff) == 0)return;
  go(A,C);
  go(C,B);
}

int main(){
  scanf("%d%d",&n,&m);
  rep(i,0,m){
    scanf("%d%d%d%d",&e[i].ff,&e[i].ss,&cost[i].ff,&cost[i].ss);
    ids[i] = i;
  }
  pll A = kruska(pll(0,1));
  pll B = kruska(pll(1,0));
 
  go(A,B);
  
  printf("%lld %lld\n",ptRes.ff,ptRes.ss);
  rep(i,0,n-1){
    printf("%d %d\n",e[res[i]].ff,e[res[i]].ss);
  }
} 

Compilation message (stderr)

timeismoney.cpp: In function 'int main()':
timeismoney.cpp:66:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   66 |   scanf("%d%d",&n,&m);
      |   ~~~~~^~~~~~~~~~~~~~
timeismoney.cpp:68:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   68 |     scanf("%d%d%d%d",&e[i].ff,&e[i].ss,&cost[i].ff,&cost[i].ss);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100