oj.uz

Submission #517126

# Submission time Handle Problem Language Result Execution time Memory
517126 2022-01-22T15:19:45 Z new_acc timeismoney (balkan11_timeismoney) C++14
45 / 100
 2000 ms 460 KB 
#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)*(y2-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
45.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 4 ms 460 KB Output is correct
9 Execution timed out 2080 ms 204 KB Time limit exceeded
10 Correct 1 ms 204 KB Output is correct
11 Execution timed out 2085 ms 204 KB Time limit exceeded
12 Execution timed out 2085 ms 204 KB Time limit exceeded
13 Execution timed out 2093 ms 204 KB Time limit exceeded
14 Execution timed out 2088 ms 204 KB Time limit exceeded
15 Execution timed out 2084 ms 204 KB Time limit exceeded
16 Execution timed out 2090 ms 332 KB Time limit exceeded
17 Execution timed out 2083 ms 332 KB Time limit exceeded
18 Execution timed out 2071 ms 332 KB Time limit exceeded
19 Execution timed out 2091 ms 460 KB Time limit exceeded
20 Execution timed out 2096 ms 460 KB Time limit exceeded