oj.uz

답안 #373518

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
373518 2021-03-05T00:13:59 Z MatheusLealV 시간이 돈 (balkan11_timeismoney) C++17
60 / 100
 2000 ms 2764 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< vector<int> > 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));
}
int cross(pii A, pii B, pii C){
	return (A.f - C.f)*(B.s - C.s) - (A.s - C.s)*(B.f - C.f);
}
auto ans = mp((int)(2e18),pii(-1,-1));
void solve(pii L, pii R){
	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;
		good=curr;
	}
	if(cross(L, R, closest.s) == 0) return;

	//checa em qual semiplano ta
	if(closest.s.f*closest.s.s >= L.f*L.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), L = get(1, 0);
	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
60.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 492 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 4 ms 748 KB Output is correct
8 Correct 26 ms 2380 KB Output is correct
9 Incorrect 1 ms 504 KB Output isn't correct
10 Incorrect 1 ms 512 KB Output isn't correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Incorrect 25 ms 492 KB Output isn't correct
15 Incorrect 11 ms 364 KB Output isn't correct
16 Incorrect 160 ms 768 KB Output isn't correct
17 Incorrect 217 ms 748 KB Output isn't correct
18 Correct 88 ms 876 KB Output is correct
19 Execution timed out 2079 ms 2764 KB Time limit exceeded
20 Execution timed out 2075 ms 2680 KB Time limit exceeded