#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));
}
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){
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";
}
}
| # |
Verdict |
Execution time |
Memory |
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 |
384 KB |
Output is correct |
| 7 |
Correct |
4 ms |
632 KB |
Output is correct |
| 8 |
Correct |
22 ms |
2380 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 |
2 ms |
364 KB |
Output is correct |
| 13 |
Correct |
2 ms |
364 KB |
Output is correct |
| 14 |
Correct |
31 ms |
492 KB |
Output is correct |
| 15 |
Correct |
21 ms |
492 KB |
Output is correct |
| 16 |
Correct |
511 ms |
748 KB |
Output is correct |
| 17 |
Correct |
553 ms |
896 KB |
Output is correct |
| 18 |
Correct |
511 ms |
876 KB |
Output is correct |
| 19 |
Execution timed out |
2085 ms |
2864 KB |
Time limit exceeded |
| 20 |
Execution timed out |
2045 ms |
2896 KB |
Time limit exceeded |
