제출 #1249242

#제출 시각아이디문제언어결과실행 시간메모리
1249242_rain_시간이 돈 (balkan11_timeismoney)C++20
100 / 100
1251 ms2704 KiB
#include<bits/stdc++.h> using namespace std; typedef long long LL; #define ii pair<int,int> #define FOR(i,a,b) for(int i = (a),_b=(b); i<=_b; ++i) #define FORD(i,a,b) for(int i = (a),_b=(b); i>=_b; --i) template<class X,class Y> bool maximize(X &x,Y y){ if (x<y) return x=y,true; else return false; } template<class X,class Y> bool minimize(X &x,Y y){ if (x>y) return x=y,true; else return false; } const int N = (int)10000; int n , m; int u[N+2] , v[N+2] , c[N+2] , t[N+2]; struct Point{ LL a,b; vector<ii>edg; Point() {}; Point(LL a,LL b) : a(a) , b(b) {}; LL F(){ return a*b; } }; Point sub(Point a,Point b){ return Point(b.a - a.a , b.b - a.b); } long double slope(Point x,Point y){ return (long double)(y.b - x.b) / (x.a - y.a); } struct EDGE{ int u,v; LL t,c; long double cost; bool operator < (const EDGE&other) const{ if (cost != other.cost) return cost<other.cost; return t*c < other.t*other.c; } }; const long double eps = 1e-9; const LL inf = (LL)1e18; #define time dasdsa class DSU{ public: vector<int>par,sz; void load_size(int n){ par = sz = vector<int>(n+2,1); iota(par.begin(),par.end(),0); return; } int Find(int u){ return par[u] == u ? par[u] : par[u] = Find(par[u]); } bool unite(int u,int v){ u = Find(u) , v = Find(v); if (u==v) return false; if (sz[u] < sz[v]) swap(u,v); par[v] = u , sz[u] += sz[v]; return true; } }; DSU dsu; Point MST(long double heso , bool write = false){ vector<EDGE> edg; FOR(i,1,m){ edg.push_back({u[i] , v[i] , t[i] , c[i] , heso * t[i] + c[i]}); } sort(edg.begin(),edg.end()); dsu.load_size(n); LL sum_time = 0 , sum_money = 0; Point sum = {0,0}; for(int i = 0; i < edg.size(); ++i){ if (dsu.unite(edg[i].u , edg[i].v)){ sum.a += edg[i].t; sum.b += edg[i].c; sum.edg.push_back({edg[i].u,edg[i].v}); } } return sum; } vector<Point>hull; void dnc(Point x,Point y){ long double slope_k = 0; if (y.b - x.b != 0){ slope_k = slope(x,y); } else slope_k = LLONG_MAX; Point nxt_p = MST(slope_k); LL cross_product = (LL)(y.a - x.a) * (nxt_p.b - x.b) - (LL)(y.b - x.b) * (nxt_p.a - x.a); if (cross_product > 0){ dnc(x,nxt_p); dnc(nxt_p,y); hull.push_back(nxt_p); } return; } int main(){ ios::sync_with_stdio(false); cin.tie(0) ; cout.tie(0); #define name "main" if (fopen(name".inp","r")){ freopen(name".inp","r",stdin); freopen(name".out","w",stdout); } cin>>n>>m; FOR(i,1,m) { cin >> u[i] >> v[i] >> t[i] >> c[i]; ++u[i] , ++v[i]; } Point min_time = MST(0) , min_money = MST(LLONG_MAX); hull.push_back(min_time); hull.push_back(min_money); dnc(min_time , min_money); vector<ii>res; LL ans = inf; LL sum_time = 0 , sum_money = 0; // cout<<hull.size()<<'\n'; for(auto&x:hull){ if (minimize(ans , x.a*x.b)){ sum_time = x.a , sum_money = x.b; res = x.edg; } } cout<<sum_time << ' '<<sum_money<<'\n'; for(auto&x:res) cout<<x.first-1<<' '<<x.second-1<<'\n'; return 0; }

컴파일 시 표준 에러 (stderr) 메시지

timeismoney.cpp: In function 'int main()':
timeismoney.cpp:122:32: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  122 |                         freopen(name".inp","r",stdin);
      |                         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
timeismoney.cpp:123:32: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  123 |                         freopen(name".out","w",stdout);
      |                         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...