답안 #517118

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
517118 2022-01-22T15:00:11 Z new_acc 시간이 돈 (balkan11_timeismoney) C++14
50 / 100
2000 ms 55356 KB
#include<bits/stdc++.h>
#define fi first
#define se second
#define rep(a, b) for(int a = 0; a < (b); a++)
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 and y1==curr.se) or (x2==curr.fi and y2==curr.se)) 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();
}
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 324 KB Output is correct
2 Correct 1 ms 316 KB Output is correct
3 Correct 1 ms 208 KB Output is correct
4 Execution timed out 2090 ms 55356 KB Time limit exceeded
5 Execution timed out 2060 ms 10952 KB Time limit exceeded
6 Execution timed out 2083 ms 11152 KB Time limit exceeded
7 Execution timed out 2081 ms 2924 KB Time limit exceeded
8 Execution timed out 2080 ms 1196 KB Time limit exceeded
9 Correct 1 ms 208 KB Output is correct
10 Correct 1 ms 208 KB Output is correct
11 Correct 1 ms 208 KB Output is correct
12 Correct 1 ms 208 KB Output is correct
13 Correct 1 ms 208 KB Output is correct
14 Correct 4 ms 320 KB Output is correct
15 Correct 3 ms 336 KB Output is correct
16 Execution timed out 2077 ms 2720 KB Time limit exceeded
17 Execution timed out 2064 ms 1588 KB Time limit exceeded
18 Execution timed out 2013 ms 1532 KB Time limit exceeded
19 Execution timed out 2069 ms 952 KB Time limit exceeded
20 Execution timed out 2053 ms 892 KB Time limit exceeded