Submission #1249252

#	Time	Username	Problem	Language	Result	Execution time	Memory
1249252		_rain_	timeismoney (balkan11_timeismoney)	C++17	100 / 100	437 ms	1224 KiB

timeismoney

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;

#define ii pair<int,int>
#define FOR(i,a,b) for(int i = (a),_b=(b); i<=_b; ++i)
#define FORD(i,a,b) for(int i = (a),_b=(b); i>=_b; --i)

template<class X,class Y>
	bool maximize(X &x,Y y){
		if (x<y) return x=y,true; else return false;
	}
template<class X,class Y>
	bool minimize(X &x,Y y){
		if (x>y) return x=y,true; else return false;
	}

const int N = (int)10000;
	int n , m;	
	int u[N+2] , v[N+2] , c[N+2] , t[N+2];

struct Point{
	LL a,b;
	long double edg;
	Point() {};
	Point(LL a,LL b,long double heso) : a(a) , b(b) , edg(heso) {};
	LL F(){
		return a*b;
	}
	bool operator == (const Point &other) const{
		return other.a == a && other.b == b;
	}
};

long double slope(Point x,Point y){
	return (long double)(y.b - x.b) / (x.a - y.a);
}

struct EDGE{
	int u,v;
	LL t,c;
	int id;
};

const long double eps = 1e-9;
const LL inf = (LL)1e18;

int par[N+2] , sz[N+2] = {};
	
	int Find(int u){
		return par[u] == u ? par[u] : par[u] = Find(par[u]);
	}
	
	bool unite(int u,int v){
		u = Find(u) , v = Find(v);
		if (u==v) return false;
		if (sz[u] < sz[v]) swap(u,v);
		par[v] = u , sz[u] += sz[v];
		return true;
	}
vector<EDGE> edg;
long double w[N+2];
Point MST(long double heso , bool write = false){
	
	FOR(i,1,m){
		w[i] = heso * t[i] + c[i];
	}
	sort(edg.begin(),edg.end(),[&](EDGE i,EDGE j){
		return w[i.id] < w[j.id];
	});
	FOR(i,1,n) par[i] = i , sz[i] = 1;
	LL sum_time = 0 , sum_money = 0;
	Point sum = Point(0,0,heso);
	for(int i = 0; i < edg.size(); ++i){
		if (unite(edg[i].u , edg[i].v)){
			sum.a += edg[i].t;
			sum.b += edg[i].c;
			if (write) cout<<edg[i].u-1<<' '<<edg[i].v-1<<'\n';
		}
	}
	return sum;
}

vector<Point>hull;

void dnc(Point x,Point y){
	long double slope_k = 0;
	if (y.b - x.b != 0){
		slope_k = slope(x,y);
	}
	else slope_k = LLONG_MAX;
	
	Point nxt_p = MST(slope_k);
	
	LL cross_product = (LL)(y.a - x.a) * (nxt_p.b - x.b) - (LL)(y.b - x.b) * (nxt_p.a - x.a);
	if (cross_product > 0){
		dnc(x,nxt_p);
		dnc(nxt_p,y);
		hull.push_back(nxt_p);
	}
	return;
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0) ; cout.tie(0);
	#define name "main"
		if (fopen(name".inp","r")){
			freopen(name".inp","r",stdin);
			freopen(name".out","w",stdout);
		}
		
		cin>>n>>m;
		FOR(i,1,m) {
			cin >> u[i] >> v[i] >> t[i] >> c[i];
			++u[i] , ++v[i];
			edg.push_back({u[i],v[i],t[i],c[i],i});
		}
		Point min_time = MST(0) , min_money = MST(LLONG_MAX);
		hull.push_back(min_time);
		if (!(min_time == min_money)){
			hull.push_back(min_money);
			dnc(min_time , min_money);
		}
		long double res = 0;
		LL ans = inf;
		LL sum_time = 0 , sum_money = 0;
		for(auto&x:hull){
			if (minimize(ans , x.a*x.b)){
				sum_time = x.a , sum_money = x.b;
				res = x.edg;
			}
		}
		cout<<sum_time << ' '<<sum_money<<'\n';
		MST(res,true);
	return 0;
}

Compilation message (stderr)

timeismoney.cpp: In function 'int main()':
timeismoney.cpp:109:32: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  109 |                         freopen(name".inp","r",stdin);
      |                         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
timeismoney.cpp:110:32: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  110 |                         freopen(name".out","w",stdout);
      |                         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100