Submission #517127

#	Time	Username	Problem	Language	Result	Execution time	Memory
517127		new_acc	timeismoney (balkan11_timeismoney)	C++14	100 / 100	391 ms	496 KiB

timeismoney

#include<bits/stdc++.h>
#define fi first
#define se second
#define rep(a, b) for(int a = 0; a < (b); a++)
#pragma GCC optimize("O2")
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
typedef vector<ll> vl;
struct item{
	int a,b,c,t,s;
};
const int N=2e2+10;
vector<pair<int,int> >xd,wyn;
item kr[1000*10+10];
ll ans=LLONG_MAX;
pair<int,int> ans2;
int fau[N];
int n,m;
int Find(int a){
	if(fau[a]==a) return a;
	return fau[a]=Find(fau[a]);
}
void Union(int a,int b){
	fau[Find(a)]=Find(fau[b]);
}
pair<int,int> mst(bool ss){
	xd.clear();
	rep(i,n) fau[i]=i;
	sort(kr,kr+m,[&](item a,item b){
		if(ss==0) return a.s<b.s;
		return a.s>b.s;
	});
	pair<int,int>res={0,0};
	rep(i,m) if(Find(kr[i].a)!=Find(kr[i].b)) Union(kr[i].a,kr[i].b),res.fi+=kr[i].t,res.se+=kr[i].c,xd.push_back({kr[i].a,kr[i].b});
	return res;
}
void rek(int x1,int y1,int x2,int y2){
	rep(i,m) kr[i].s=kr[i].c*(x2-x1)+kr[i].t*(y1-y2);
	pair<int,int> curr=mst(1);
	if((x1-curr.fi)*(y2-curr.se)-(x2-curr.fi)*(y1-curr.se)==0) return;
	if(ans>=(ll)(curr.fi)*(ll)(curr.se)) ans=(ll)(curr.fi)*(ll)(curr.se),wyn=xd,ans2={curr.fi,curr.se};
	rek(x1,y1,curr.fi,curr.se);
	rek(curr.fi,curr.se,x2,y2);
}
void solve(){
	cin>>n>>m;
	rep(i,m) cin>>kr[i].a>>kr[i].b>>kr[i].t>>kr[i].c;
	rep(i,m) kr[i].s=kr[i].c;
	pair<int,int> a=mst(0);
	wyn=xd,ans2={a.fi,a.se},ans=(ll)a.fi*(ll)a.se;
	rep(i,m) kr[i].s=kr[i].t;
	pair<int,int>b=mst(0);
	if((ll)b.fi*(ll)b.se<ans) ans=(ll)b.fi*(ll)b.se,ans2={b.fi,b.se},wyn=xd;
	rek(a.fi,a.se,b.fi,b.se);
	cout<<ans2.fi<<" "<<ans2.se<<"\n";
	for(auto u:wyn) cout<<u.fi<<" "<<u.se<<"\n";
}
int main(){
	ios_base::sync_with_stdio(0),cin.tie(0);
	solve();
}

• Subtask 1: 100 / 100