제출 #37064

#제출 시각아이디문제언어결과실행 시간메모리
37064Angelos시간이 돈 (balkan11_timeismoney)C++11
0 / 100
13 ms2176 KiB
#include <bits/stdc++.h> using namespace std; typedef pair<int,int> pi; struct edge{int s,e,x,y;}adj[10004]; int N , M; typedef long long lint; int mc1 , mc2 , mx = 1e9 , my = 1e9; struct disj{ int pa[204]; void init(int n){for(int i=0; i<n; i++) pa[i] = i;} int findd(int x){return pa[x] = (pa[x] == x ? x : findd(pa[x]));} bool uni(int a , int b){ int p = findd(a) , q = findd(b); if(p == q) return 0; pa[q] = p;return 1; } }disj; bool ccw(pi a, pi b, pi c){ int dx1 = b.first - a.first; int dy1 = b.second - a.second; int dx2 = c.first - a.first; int dy2 = c.second - a.second; return 1ll * dx1 * dy2 >= 1ll * dy1 * dx2; } pi get_mst(int c1 , int c2 , int is){ disj.init(N); sort(adj , adj+N , [&](const edge &aa , const edge &bb){ return (1ll * aa.x * c1) + (1ll * aa.y * c2) < (1ll * bb.x * c1) + (1ll * bb.y * c2); }); pi tmp(0,0); for(int i=0; i<M; i++){ if(disj.uni(adj[i].s , adj[i].e)){ tmp.first += adj[i].x; tmp.second += adj[i].y; if(is) cout << adj[i].x << " " << adj[i].y << endl; } } if(1ll * mx * my > 1ll * tmp.first * tmp.second){ mx = tmp.first , my = tmp.second; mc1 = c1 , mc2 = c2; } return tmp; } void solve(pi u , pi l){ pi n = get_mst(u.second - l.second , l.first - u.first , 0); if(!ccw(l,n,u)) solve(u,n) , solve(n,l); } int main(){ cin >> N >> M; for(int i=0; i<M; i++) cin >> adj[i].s >> adj[i].e >> adj[i].x >> adj[i].y; pi upper = get_mst(1,0,0); pi lower = get_mst(0,1,0); solve(upper , lower); cout << mx << " " << my << endl; get_mst(mc1 , mc2 , 1); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...