oj.uz

답안 #373822

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
373822 2021-03-05T20:44:03 Z MatheusLealV 시간이 돈 (balkan11_timeismoney) C++14
90 / 100
 2000 ms 2216 KB 
#include <bits/stdc++.h>
#define N 210
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
using namespace std;
typedef pair<int, int> pii;
 
int n, m;
vector<pair<int, pii> > grafo[N];
int pai[N], peso[N];
int Find(int x){
	if(x == pai[x]) return x;
	return pai[x] = Find(pai[x]);
}
bool join(int a, int b){
	a = Find(a);
	b = Find(b);
	if(a==b) return 0;
	if(peso[a]<peso[b])swap(a,b);
	pai[b]=a;
	if(peso[a]==peso[b])peso[a]++;
	return 1;
}
vector< pii > good, curr;
pair<int,pii> get(int A, int B){
	// cout<<"sss "<<A<<" "<<B<<"\n";
	vector< array<int, 5> > arestas;
	curr.clear();
	for(int i = 1; i <= n; i++){
		pai[i]=i,peso[i] = 0;
		for(auto v: grafo[i]){
			int cost = A*v.s.f + B*v.s.s;
			arestas.pb({cost, v.s.f, v.s.s, i, v.f});
		}
	}
	int x = 0, y = 0, resp=0;
	sort(all(arestas));
	for(auto e: arestas){
		int cost = e[0], xi = e[1], yi = e[2], a = e[3], b = e[4];
		if(join(a, b)){
			curr.pb({a, b});
			x += xi;
			y += yi;
			resp += cost;
		}
	}
	return mp(resp, pii(x, y));
}
bool cross(pii A, pii B, pii C){
	return 1LL*(A.f - C.f)*(B.s - C.s) - 1LL*(A.s - C.s)*(B.f - C.f) != 0LL;
}
auto ans = mp((int)(1e9),pii(-1,-1));
void solve(pii L, pii R){
	//cout<<"A "<<L.f<<" "<<L.s<<" // "<<R.f<<" "<<R.s<<"\n";
	pii slope = {(L.s - R.s), (R.f - L.f)};
	auto closest = get(slope.f, slope.s);
	if(closest.s.f * closest.s.s < ans.f){
		ans.f = closest.s.f*closest.s.s;
		ans.s = closest.s;
		swap(good, curr);
	}
	if(!cross(L, R, closest.s)) return;
 
	//checa em qual semiplano ta
	if(slope.f*closest.s.f + slope.s*closest.s.s >= slope.f*L.f + slope.s*L.s) return; 
	if(slope.f*closest.s.f + slope.s*closest.s.s >= slope.f*R.f + slope.s*R.s) return; 
	solve(L, closest.s),solve(closest.s, R);
}
int32_t main(){
	ios::sync_with_stdio(false); cin.tie(0);
	cin>>n>>m;
	for(int i = 1; i <= m; i++){
		int a, b,c,d;
		cin>>a>>b>>c>>d;
		a++,b++;
		grafo[a].push_back({b, {c, d}});
		grafo[b].push_back({a, {c, d}});
	}
	auto R = get(0, 1);
	if(R.s.f*R.s.s < ans.f){
		ans.f = R.s.f*R.s.s;
		ans.s=R.s;
		swap(good, curr);
	}
	auto L = get(1, 0);
	if(L.s.f*L.s.s < ans.f){
		ans.f = L.s.f*L.s.s;
		ans.s=L.s;
		swap(good, curr);
	}
	solve(L.s, R.s);
	cout<<ans.s.f<<" "<<ans.s.s<<"\n";
	for(auto e: good){
		cout<<e.f-1<<" "<<e.s-1<<"\n";
	}
}

Subtask #1
90.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 3 ms 620 KB Output is correct
8 Correct 16 ms 1888 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 16 ms 364 KB Output is correct
15 Correct 11 ms 364 KB Output is correct
16 Correct 296 ms 868 KB Output is correct
17 Correct 314 ms 784 KB Output is correct
18 Correct 311 ms 984 KB Output is correct
19 Execution timed out 2082 ms 1984 KB Time limit exceeded
20 Execution timed out 2037 ms 2216 KB Time limit exceeded