#pragma GCC optimize("Ofast")
//#pragma GCC optimization ("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define vi vector<int>
#define vv vector<vi>
#define pb push_back
#define pi pair<int,int>
#define vvp vector<vector<pi>>
int n,m;
struct edge{
int a,b,t,c,idx;
};
vector<edge> edges;
vector<int> weight;
pi sol;
vector<pi> mstsol;
vector<pi> currmst;
struct dsu{
vi par,size;
int find(int i){
return par[i] == i ? i : par[i] = find(par[i]);
}
void uni(int a, int b){
a = find(a); b = find(b);
if(a == b) return;
if(size[a] < size[b]) swap(a,b);
size[a] += size[b];
par[b] = a;
}
dsu(int n){
par.resize(n);
iota(par.begin(), par.end(), 0);
size.resize(n,1);
}
};
pi solve(){
sort(edges.begin(), edges.end(), [&](const edge &a, const edge &b){
return weight[a.idx] < weight[b.idx];
});
dsu d(n);
int tcost = 0, ccost = 0;
currmst.clear();
for(int i = 0; i < m; i++){
edge &a = edges[i];
if(d.find(a.a) != d.find(a.b)){
tcost += a.t; ccost += a.c;
d.uni(a.a, a.b);
currmst.pb({a.a, a.b});
}
}
return {tcost, ccost};
}
pi sub(pi a, pi b){
return {a.first - b.first, a.second - b.second};
}
bool sopra(pi a, pi b){
return (a.first * b.second - a.second * b.first > 0);
}
int main()
{
cin.tie(0); cin.sync_with_stdio(0);cout.tie(0); cout.sync_with_stdio(0);
cin>>n>>m;
edges.resize(m); weight.resize(m);
for(int i = 0; i < m; i++){
edge a;
cin>>a.a>>a.b>>a.t>>a.c;
a.idx = i;
edges[i] = a;
}
//soluzione ottimale per t
for(int i = 0; i < m; i++){
int idx = edges[i].idx;
weight[idx] = edges[i].t;
}
pi a = solve();
pi best = a;
mstsol = currmst;
//soluzione ottimale per c
for(int i = 0; i < m; i++){
int idx = edges[i].idx;
weight[idx] = edges[i].c;
}
pi b = solve();
//swap a e b se b best
//area triangolo negativa quindi minimizzo per la migliore
if((ll)best.first * best.second > (ll)b.first * b.second){
best = b;
mstsol = currmst;
swap(a,b);
}
stack<pair<pi,pi>> s; s.push({a,b});
while(!s.empty()){
//change wwight
a = s.top().first, b = s.top().second;
s.pop();
for(int i = 0; i < m; i++){
int idx = edges[i].idx;
weight[idx] = edges[i].c * (b.first - a.first) - edges[i].t * (b.second - a.second);
}
//run mst
pi p = solve();
//sopra retta a-b, punto peggiore
if(sopra(sub(b,a), sub(p,a)) ){
continue;
}
if((ll)best.first * best.second > (ll)p.first * p.second){
best = p;
mstsol = currmst;
}
s.push({a,p});
s.push({p,b});
}
cout << best.first << " " << best.second << "\n";
for(pi &a:mstsol){
cout << a.first << " " << a.second << "\n";
}
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
2085 ms |
5512 KB |
Time limit exceeded |
| 2 |
Runtime error |
1857 ms |
65536 KB |
Execution killed with signal 9 |
| 3 |
Execution timed out |
2082 ms |
47680 KB |
Time limit exceeded |
| 4 |
Execution timed out |
2089 ms |
14924 KB |
Time limit exceeded |
| 5 |
Execution timed out |
2084 ms |
3744 KB |
Time limit exceeded |
| 6 |
Execution timed out |
2089 ms |
3576 KB |
Time limit exceeded |
| 7 |
Execution timed out |
2093 ms |
1000 KB |
Time limit exceeded |
| 8 |
Execution timed out |
2079 ms |
944 KB |
Time limit exceeded |
| 9 |
Runtime error |
1932 ms |
65536 KB |
Execution killed with signal 9 |
| 10 |
Execution timed out |
2089 ms |
30792 KB |
Time limit exceeded |
| 11 |
Execution timed out |
2089 ms |
48308 KB |
Time limit exceeded |
| 12 |
Execution timed out |
2092 ms |
16252 KB |
Time limit exceeded |
| 13 |
Execution timed out |
2092 ms |
16252 KB |
Time limit exceeded |
| 14 |
Execution timed out |
2084 ms |
3668 KB |
Time limit exceeded |
| 15 |
Execution timed out |
2085 ms |
2920 KB |
Time limit exceeded |
| 16 |
Execution timed out |
2086 ms |
716 KB |
Time limit exceeded |
| 17 |
Execution timed out |
2090 ms |
828 KB |
Time limit exceeded |
| 18 |
Execution timed out |
2084 ms |
616 KB |
Time limit exceeded |
| 19 |
Execution timed out |
2095 ms |
556 KB |
Time limit exceeded |
| 20 |
Execution timed out |
2080 ms |
700 KB |
Time limit exceeded |
