#include <bits/stdc++.h>
#define sz(X) (int)((X).size())
#define entire(X) X.begin(),X.end()
using namespace std; typedef long long ll;
void OJize(){cin.tie(NULL);ios_base::sync_with_stdio(false);}
template <class T1, class T2>ostream&operator<<(ostream &os,pair<T1,T2>const&x){os<<'('<<x.first<<", "<<x.second<<')';return os;}
template <class Ch, class Tr, class Container>basic_ostream<Ch,Tr>&operator<<(basic_ostream<Ch,Tr>&os,Container const&x){for(auto&y:x)os<<y<<" ";return os;}
typedef pair<ll,ll> pll;
// positive -> ccw; negative -> cw; 0 -> collinear
ll ccw(pll a, pll b, pll c){
auto [ax,ay] = a; auto [bx,by] = b; auto [cx,cy] = c;
return (bx-ax)*(cy-ay) - (by-ay)*(cx-ax);
}
struct disjointSet{
vector<int> par;
disjointSet(int n): par(n) {iota(entire(par), 0);}
void un(int x, int y){par[fd(x)] = fd(y);} // yr becomes parent
int fd(int x){return par[x]!=x? (par[x]=fd(par[x])) : x;}
};
typedef tuple<int,int,ll,ll> EDGE;
int n;
vector<EDGE> edges;
tuple<ll, ll, vector<pair<int,int>>>
mst(ll T, ll C){
sort(entire(edges), [&](const EDGE &e1, const EDGE &e2){
auto [a1,b1,t1,c1] = e1;
auto [a2,b2,t2,c2] = e2;
return T*t1 + C*c1 < T*t2 + C*c2;
});
ll ts = 0, cs = 0;
disjointSet DS(n+1);
vector<pair<int,int>> ans;
for(auto [a,b,t,c]: edges){
if(DS.fd(a) == DS.fd(b)) continue;
DS.un(a, b), ts+= t, cs+= c;
ans.push_back({a,b});
}
return {ts, cs, ans};
}
tuple<ll,ll,ll> hullsearch(pll l, pll r){
auto [lt,lc] = l; auto [rt,rc] = r;
tuple<ll,ll,ll> ltup = {lt*lc,lt,lc}, rtup = {rt*rc,rt,rc};
auto ans = min(ltup, rtup);
auto [mt,mc,_] = mst(lc-rc, rt-lt);
pll m = {mt,mc};
if(ccw(r, m, l) < 0){
ans = min(ans, hullsearch(l, m));
ans = min(ans, hullsearch(m, r));
}
return ans;
}
int main(){OJize();
int m; cin>>n>>m;
for(int i=0; i<m; i++){
int a,b,t,c; cin>>a>>b>>t>>c;
edges.push_back({a,b,t,c});
}
auto [x0,y0,_] = mst(1, 0);
auto [x1,y1,__] = mst(0, 1);
auto [tc,t,c] = hullsearch({x0,y0}, {x1,y1});
cout<<t<<' '<<c<<"\n";
auto [___,____,TREE] = mst(t, c);
for(auto [a,b]: TREE) cout<<a<<' '<<b<<'\n';
}
Compilation message
timeismoney.cpp: In lambda function:
timeismoney.cpp:30:26: warning: unused variable 'a1' [-Wunused-variable]
auto [a1,b1,t1,c1] = e1;
^
timeismoney.cpp:30:26: warning: unused variable 'b1' [-Wunused-variable]
timeismoney.cpp:31:26: warning: unused variable 'a2' [-Wunused-variable]
auto [a2,b2,t2,c2] = e2;
^
timeismoney.cpp:31:26: warning: unused variable 'b2' [-Wunused-variable]
timeismoney.cpp: In function 'std::tuple<long long int, long long int, long long int> hullsearch(pll, pll)':
timeismoney.cpp:49:18: warning: unused variable '_' [-Wunused-variable]
auto [mt,mc,_] = mst(lc-rc, rt-lt);
^
timeismoney.cpp: In function 'int main()':
timeismoney.cpp:64:18: warning: unused variable '_' [-Wunused-variable]
auto [x0,y0,_] = mst(1, 0);
^
timeismoney.cpp:65:19: warning: unused variable '__' [-Wunused-variable]
auto [x1,y1,__] = mst(0, 1);
^
timeismoney.cpp:66:17: warning: unused variable 'tc' [-Wunused-variable]
auto [tc,t,c] = hullsearch({x0,y0}, {x1,y1});
^
timeismoney.cpp:68:24: warning: unused variable '___' [-Wunused-variable]
auto [___,____,TREE] = mst(t, c);
^
timeismoney.cpp:68:24: warning: unused variable '____' [-Wunused-variable]
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
384 KB |
Output is correct |
| 2 |
Correct |
5 ms |
384 KB |
Output is correct |
| 3 |
Correct |
5 ms |
384 KB |
Output is correct |
| 4 |
Correct |
5 ms |
384 KB |
Output is correct |
| 5 |
Correct |
5 ms |
384 KB |
Output is correct |
| 6 |
Correct |
5 ms |
384 KB |
Output is correct |
| 7 |
Correct |
6 ms |
512 KB |
Output is correct |
| 8 |
Correct |
10 ms |
960 KB |
Output is correct |
| 9 |
Incorrect |
4 ms |
384 KB |
Output isn't correct |
| 10 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
| 11 |
Incorrect |
5 ms |
288 KB |
Output isn't correct |
| 12 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
| 13 |
Correct |
5 ms |
384 KB |
Output is correct |
| 14 |
Incorrect |
10 ms |
384 KB |
Output isn't correct |
| 15 |
Incorrect |
8 ms |
384 KB |
Output isn't correct |
| 16 |
Incorrect |
65 ms |
512 KB |
Output isn't correct |
| 17 |
Incorrect |
71 ms |
512 KB |
Output isn't correct |
| 18 |
Incorrect |
67 ms |
432 KB |
Output isn't correct |
| 19 |
Incorrect |
496 ms |
1020 KB |
Output isn't correct |
| 20 |
Incorrect |
501 ms |
1088 KB |
Output isn't correct |
