#include<bits/stdc++.h>
#define int long long
#define pb push_back
#define fast ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
#define MOD 1000000007
#define INF 1e18
#define fi first
#define se second
#define endl "\n"
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define FORD(i,a,b) for(int i=a;i>=b;i--)
#define sz(a) ((int)(a).size())
#define pi 3.14159265359
#define TASKNAME ""
template<typename T> bool maximize(T &res, const T &val) { if (res < val){ res = val; return true; }; return false; }
template<typename T> bool minimize(T &res, const T &val) { if (res > val){ res = val; return true; }; return false; }
using namespace std;
typedef pair<int,int> ii;
typedef pair<int,ii> iii;
typedef vector<int> vi;
const int MAXN = 2e2 + 9;
vector<ii> ValidEdge;
int n,m;
int sumtime = 0, sumcost = 0, numcmp;
struct DSU{
vector<int> par,ranking;
DSU(int n = 0){
par.resize(n+1);
ranking.resize(n+1,1);
iota(par.begin(),par.end(),0);
}
int root(int u){
if (par[u] == u) return u;
else return par[u] = root(par[u]);
}
bool unite(int u,int v){
u = root(u);
v = root(v);
if (u != v){
if (ranking[u] <= ranking[v]) swap(u,v);
ranking[u] += ranking[v];
par[v] = u;
return true;
}
return false;
}
};
struct Edge{
int u,v,w;
ii TimeCost;
Edge(int _u = 0,int _v = 0,int _w = 0, ii _TimeCost = {0,0}): u(_u), v(_v), w(_w), TimeCost(_TimeCost) {}
Edge(int _u = 0,int _v = 0, ii _TimeCost = {0,0}): u(_u), v(_v), TimeCost(_TimeCost) {}
};
typedef pair<ii,vector<Edge>> MST;
vector<Edge> Link,weight;
vector<Edge> e;
ii kruskal(vector<Edge> &edge, bool printed){
DSU DSU(n);
int t = 0, c = 0;
for(auto e: edge){
if (DSU.unite(e.u,e.v)){
t += e.TimeCost.fi;
c += e.TimeCost.se;
if (printed) cout<<e.u<<' '<<e.v<<endl;
}
}
return {t,c};
}
ii operator - (const ii &a, const ii &b){
return ii(a.fi - b.fi, a.se - b.se);
}
int ccw(ii a,ii b,ii c){
b = b - a;
c = c - a;
return b.fi * c.se - c.fi * b.se;
}
ii ans, tr1, tr2;
void update(ii &ans,ii t,ii A, ii B){
if (ans.fi * ans.se > t.fi * t.se){
ans = t;
tr1 = A;
tr2 = B;
}
}
bool cmp(Edge a,Edge b){
return a.w < b.w;
}
main()
{
fast;
if (fopen(TASKNAME".inp","r")){
freopen(TASKNAME".inp","r",stdin);
freopen(TASKNAME".out","w",stdout);
}
cin>>n>>m;
for(int i=1;i<=m;i++){
int u,v,t,c;
cin>>u>>v>>t>>c;
Link.pb(Edge(u,v,{t,c}));
}
for(auto &e: Link){
e.w = e.TimeCost.fi;
}
sort(Link.begin(),Link.end(),cmp);
ii A = kruskal(Link,0);
for(auto &e: Link){
e.w = e.TimeCost.se;
}
sort(Link.begin(),Link.end(),cmp);
ii B = kruskal(Link,0);
queue<pair<ii,ii>> q;
weight = Link;
q.push({A,B});
ii ans = {1e9,1e9};
update(ans, A, ii(-1,-1), ii(-1,-1));
update(ans, B, ii(-1,-1), ii(-1,-1));
while(!q.empty()){
ii A = q.front().fi;
ii B = q.front().se;
q.pop();
weight.clear();
for(int i=0;i<Link.size();i++){
Link[i].w = Link[i].TimeCost.se * (B.fi - A.fi) - Link[i].TimeCost.fi * (B.se - A.se);
}
sort(Link.begin(),Link.end(),cmp);
ii P = kruskal(Link,0);
update(ans, P, A, B);
if (ccw(A,B,P) >= 0) continue;
q.push({A,P});
q.push({P,B});
}
if (ans == A){
cout<<ans.fi<<' '<<ans.se<<endl;
for(int i=0;i<Link.size();i++){
Link[i].w = Link[i].TimeCost.fi;
}
sort(Link.begin(),Link.end(),cmp);
kruskal(Link,1);
}
else if (ans == B){
cout<<ans.fi<<' '<<ans.se<<endl;
for(int i=0;i<Link.size();i++){
Link[i].w = Link[i].TimeCost.se;
}
sort(Link.begin(),Link.end(),cmp);
kruskal(Link,1);
}
else{
cout<<ans.fi<<' '<<ans.se<<endl;
for(int i=0;i<Link.size();i++){
Link[i].w = Link[i].TimeCost.se * (tr2.fi - tr1.fi) - Link[i].TimeCost.fi * (tr2.se - tr1.se);
}
sort(Link.begin(),Link.end(),cmp);
kruskal(Link,1);
}
}
/*
Ta can tim diem phai nhat so voi AB.
de tam giac co dien tich lon nhat.
-2ABP = AB x AP = (xB - xA) * (yP - yA) - (xP - xA) * (yB - yA)
= xB * yP - xB * yA - xA * yP - xP * yB + xP * yA + xA * yB
= yP * (xB - xA) - xP * (yB - yA);
*/
/*
Nhan xet la chi co 1 so so dinh thuc su dang can nhac.
*/
Compilation message
timeismoney.cpp:91:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
91 | main()
| ^~~~
timeismoney.cpp: In function 'int main()':
timeismoney.cpp:125:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<Edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
125 | for(int i=0;i<Link.size();i++){
| ~^~~~~~~~~~~~
timeismoney.cpp:137:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<Edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
137 | for(int i=0;i<Link.size();i++){
| ~^~~~~~~~~~~~
timeismoney.cpp:145:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<Edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
145 | for(int i=0;i<Link.size();i++){
| ~^~~~~~~~~~~~
timeismoney.cpp:153:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<Edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
153 | for(int i=0;i<Link.size();i++){
| ~^~~~~~~~~~~~
timeismoney.cpp:95:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
95 | freopen(TASKNAME".inp","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
timeismoney.cpp:96:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
96 | freopen(TASKNAME".out","w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
1 ms |
348 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Correct |
1 ms |
600 KB |
Output is correct |
| 8 |
Correct |
6 ms |
1364 KB |
Output is correct |
| 9 |
Correct |
0 ms |
348 KB |
Output is correct |
| 10 |
Correct |
1 ms |
348 KB |
Output is correct |
| 11 |
Correct |
1 ms |
344 KB |
Output is correct |
| 12 |
Correct |
0 ms |
348 KB |
Output is correct |
| 13 |
Correct |
1 ms |
348 KB |
Output is correct |
| 14 |
Correct |
6 ms |
344 KB |
Output is correct |
| 15 |
Correct |
4 ms |
348 KB |
Output is correct |
| 16 |
Correct |
89 ms |
604 KB |
Output is correct |
| 17 |
Correct |
94 ms |
600 KB |
Output is correct |
| 18 |
Correct |
91 ms |
852 KB |
Output is correct |
| 19 |
Correct |
785 ms |
1364 KB |
Output is correct |
| 20 |
Correct |
801 ms |
1364 KB |
Output is correct |
