//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define int ll
#define pii pair<int,int>
#define f first
#define s second
#define all(x) x.begin(),x.end()
#define _ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
void setIO(string s) {
freopen((s + ".in").c_str(), "r", stdin);
freopen((s + ".out").c_str(), "w", stdout);
}
pii operator-(pii a,pii b){
return pii(a.f-b.f,a.s-b.s);
}
ll cross(pii a,pii b){
return 1ll*a.f*b.s-1ll*a.s*b.f;
}
bool ori(pair<int,int> a,pair<int,int> b,pair<int,int> c){
ll res=cross(b-a,c-a);
return (res>0?1:0);
}
const ll inf=(ll)1e18;
signed main(){_
int n,m;
cin>>n>>m;
int X,Y;
struct DSU{
vector<int> e;
DSU(int n){
e=vector<int>(n,-1);
}
void reset(int n){
e=vector<int>(n,-1);
}
int find(int x){
return (e[x]<0?x:e[x]=find(e[x]));
}
bool unite(int a,int b){
a=find(a);
b=find(b);
if(a==b) return false;
if(e[a]>e[b]) swap(a,b);
e[a]+=e[b];
e[b]=a;
return true;
}
};
struct edge{
int a,b,x,y;
edge(){}
edge(int _a,int _b,int _x,int _y){
a=_a;
b=_b;
x=_x;
y=_y;
}
};
auto comp=[&](edge e1,edge e2){
return e1.x*X+e1.y*Y<e2.x*X+e2.y*Y;
};
vector<edge> E;
for(int i=0;i<m;i++){
int a,b,x,y;
cin>>a>>b>>x>>y;
E.push_back(edge(a,b,x,y));
}
vector<pair<int,int>> tmp;
DSU dsu(n);
map<pair<int,int>,int> mp;
auto get=[&](int _X,int _Y){
X=_X;
Y=_Y;
sort(all(E),comp);
int aX=0,aY=0;
dsu.reset(n);
tmp.clear();
for(auto e:E){
if(dsu.unite(e.a,e.b)){
aX+=e.x;
aY+=e.y;
tmp.push_back({e.a,e.b});
}
}
mp[{aX,aY}]=1;
return make_pair(aX,aY);
};
vector<pair<pair<int,int>,pair<int,int>>> vec;
pair<int,int> A=get(1,0);
pair<int,int> B=get(0,1);
vec.push_back({A,{X,Y}});
if(mp.find(B)==mp.end()) vec.push_back({B,{X,Y}});
function<void(pair<int,int>,pair<int,int>)> go=[&](pair<int,int> p1,pair<int,int> p2){
auto p=get(p1.s-p2.s,p2.f-p1.f);
if(!ori(p2,p1,p)) return;
if(mp.find(p)==mp.end()) vec.push_back({p,{X,Y}});
go(p1,p);
go(p,p2);
};
go(A,B);
pair<ll,pair<pair<int,int>,pair<int,int>>> ans={inf,{{0,0},{0,0}}};
for(auto v:vec){
ans=min(ans,{1ll*v.f.f*v.f.s,v});
}
auto p=get(ans.s.s.f,ans.s.s.s);
cout<<ans.s.f.f<<' '<<ans.s.f.s<<'\n';
for(auto v:tmp){
cout<<v.f<<' '<<v.s<<'\n';
}
return 0;
}
//maybe its multiset not set
//yeeorz
//diaoborz
Compilation message (stderr)
timeismoney.cpp: In function 'void setIO(std::string)':
timeismoney.cpp:16:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
16 | freopen((s + ".in").c_str(), "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
timeismoney.cpp:17:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
17 | freopen((s + ".out").c_str(), "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |