#include "bits/stdc++.h"
using namespace std;
#define all(x) begin(x),end(x)
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { string sep; for (const T &x : v) os << sep << x, sep = " "; return os; }
#define debug(a) cerr << "(" << #a << ": " << a << ")\n";
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pi;
const int mxN = 200+1, mxM=1e4, oo = 1e9;
typedef complex<int> pt;
#define X real()
#define Y imag()
auto cross(pt u, pt v) {return (ll)u.X*v.Y-(ll)u.Y*v.X;}
auto sgn(ll a) {return a==0?0:(a>0?1:-1);}
auto ccw(pt p1, pt p2, pt p3) {auto u = p2-p1, v = p3-p2;return cross(u,v);}
auto in(pt p1, pt p2) {return (ll)p1.X*p2.X+(ll)p1.Y*p2.Y;}
auto norm(pt p) {return (ll)p.X*p.X+(ll)p.Y*p.Y;}
void read(pt& p) {
int a,b; cin >> a >> b;
p = {a,b};
}
struct DSU{
vector<int> sz,parent;
int components;
DSU(int n) {
sz.assign(n,1);
components = n;
parent.resize(n);
for(int i=0;i<n;++i) parent[i]=i;
}
void link(int a, int b) {
components--;
if(sz[a]<sz[b]) {
swap(a,b);
}
sz[a] = max(sz[a],sz[b]+1);
parent[b] = a;
}
void unite(int a, int b) {
int pa = find(a),pb = find(b);
if(pa!=pb) link(pa,pb);
}
int find(int a) {
if(a==parent[a]) return a;
return parent[a] = find(parent[a]);
}
};
ll ft,fc;
struct edge{
int a,b,t,c;
bool operator<(const edge& o) const {
return ft*t+fc*c < ft*o.t+fc*o.c;
}
};
int n,m;
edge edges[mxM];
pt kruskal() {
DSU dsu(n);
sort(edges,edges+m);
pt ans = 0;
for(int j=0;j<m;++j) {
auto& e = edges[j];
int pa = dsu.find(e.a), pb=dsu.find(e.b);
if(pa!=pb) {
ans+=pt{e.t,e.c};
dsu.link(pa,pb);
}
if(dsu.components==1) break;
}
return ans;
}
int bestfc=0, bestft=1, best=oo;
complex<int> bestp=0;
void solve(pt ul, pt rd) {
ft = ul.Y-rd.Y;
fc = rd.X-ul.X;
auto nw = kruskal();
int ans = nw.X*nw.Y;
if(ans<best) {
bestp = nw;
best = ans;
bestfc = fc;
bestft = ft;
}
if(ccw(ul,rd,nw)==0) return;
solve(ul,nw), solve(nw,rd);
}
int main() {
cin >> n>>m;
for(int i=0;i<m;++i) {
int a,b,t,c; cin >> a >> b >> t >> c;
edges[i] = {a,b,t,c};
}
ft = 1, fc = 0;
auto p1 = kruskal();
ft = 0, fc = 1;
auto p2 = kruskal();
solve(p1,p2);
cout << bestp.X << ' ' << bestp.Y << '\n';
ft = bestft;
fc = bestfc;
DSU dsu(n);
sort(edges,edges+m);
pt ans = 0;
for(int j=0;j<m;++j) {
auto& e = edges[j];
int pa = dsu.find(e.a), pb=dsu.find(e.b);
if(pa!=pb) {
ans+=pt{e.t,e.c};
dsu.link(pa,pb);
cout << e.a << ' ' << e.b << '\n';
}
if(dsu.components==1) break;
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 3 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 4 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 5 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 6 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 7 |
Incorrect |
4 ms |
364 KB |
Output isn't correct |
| 8 |
Incorrect |
11 ms |
512 KB |
Output isn't correct |
| 9 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 10 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 11 |
Correct |
1 ms |
364 KB |
Output is correct |
| 12 |
Correct |
1 ms |
364 KB |
Output is correct |
| 13 |
Correct |
1 ms |
364 KB |
Output is correct |
| 14 |
Correct |
4 ms |
364 KB |
Output is correct |
| 15 |
Correct |
3 ms |
364 KB |
Output is correct |
| 16 |
Correct |
52 ms |
384 KB |
Output is correct |
| 17 |
Correct |
54 ms |
364 KB |
Output is correct |
| 18 |
Correct |
49 ms |
364 KB |
Output is correct |
| 19 |
Correct |
423 ms |
620 KB |
Output is correct |
| 20 |
Correct |
442 ms |
528 KB |
Output is correct |
