Submission #1249242

#	Time	Username	Problem	Language	Result	Execution time	Memory
1249242		_rain_	timeismoney (balkan11_timeismoney)	C++20	100 / 100	1251 ms	2704 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;
	vector<ii>edg;
	Point() {};
	Point(LL a,LL b) : a(a) , b(b) {};
	LL F(){
		return a*b;
	}
};

Point sub(Point a,Point b){
	return Point(b.a - a.a , b.b - a.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;
	long double cost;
	bool operator < (const EDGE&other) const{
		if (cost != other.cost) return cost<other.cost;
		return t*c < other.t*other.c;
	}
};

const long double eps = 1e-9;
const LL inf = (LL)1e18;
#define time dasdsa

class DSU{
public:
	vector<int>par,sz;
	
	void load_size(int n){
		par = sz = vector<int>(n+2,1);
		iota(par.begin(),par.end(),0);
		return;
	}
	
	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;
	}
};
DSU dsu;

Point MST(long double heso , bool write = false){
	vector<EDGE> edg;
	FOR(i,1,m){
		edg.push_back({u[i] , v[i] , t[i] , c[i] , heso * t[i] + c[i]});
	}
	sort(edg.begin(),edg.end());
	dsu.load_size(n);
	LL sum_time = 0 , sum_money = 0;
	Point sum = {0,0};
	for(int i = 0; i < edg.size(); ++i){
		if (dsu.unite(edg[i].u , edg[i].v)){
			sum.a += edg[i].t;
			sum.b += edg[i].c;
			sum.edg.push_back({edg[i].u,edg[i].v});
		}
	}
	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];
		}
		Point min_time = MST(0) , min_money = MST(LLONG_MAX);
		hull.push_back(min_time);
		hull.push_back(min_money);
		dnc(min_time , min_money);
		vector<ii>res;
		LL ans = inf;
		LL sum_time = 0 , sum_money = 0;
//		cout<<hull.size()<<'\n';
		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';
		for(auto&x:res) cout<<x.first-1<<' '<<x.second-1<<'\n';
	return 0;
}

Compilation message (stderr)

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

• Subtask 1: 100 / 100