#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();
}
| # |
Verdict |
Execution time |
Memory |
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 |
