oj.uz

답안 #654924

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
654924 2022-11-02T01:54:38 Z jeroenodb Ceste (COCI17_ceste) C++14
160 / 160
 314 ms 16968 KB 
#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 = 1e5+1, 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;}
bool comp(const pt& a, const pt& b) { return a.X<b.X or (a.X==b.X and a.Y > b.Y);}
void read(pt& p) {
    int a,b; cin >> a >> b;
    p = {a,b};
}
struct cmp {
    bool operator()(const pt& a, const pt& b)const {
        return comp(a,b);
    }
};
int main() {
    // freopen("ceste.in","r",stdin);
    int n,m; cin >> n >> m;
    vector<vector<array<int,3>>> adj(n);
    for(int i=0;i<m;++i) {
        int a,b,t,c; cin >> a >> b >> t >> c;
        --a,--b;
        adj[a].push_back({b,t,c});
        adj[b].push_back({a,t,c});
    }
    struct Hull {
        set<pt,cmp> s;
        bool inside(pt p) {
            if(s.empty()) return false;
            auto it = s.lower_bound(p);
            if(it==s.end()) {
                --it;
                return it->Y <= p.Y;
            } else if(it==s.begin()) {
                return (*it==p);
            }
            auto pit = prev(it);
            return ccw(*pit,p,*it)<=0;
        }
        bool corner(pt p) {
            return s.count(p);
        }
        void insert(pt p) {
            if(inside(p)) return;
            auto [it,b] = s.insert(p);
            assert(b);
            if(it!=s.begin()) {
                auto pit = prev(it);
                while(pit!=s.begin()) {
                    auto ppit = prev(pit);
                    if(ccw(*ppit,*pit,p)<=0) {
                        s.erase(pit);
                        pit = ppit;
                    } else break;
                }
                
            }
            if(next(it)!=s.end()) {
                auto pit = next(it);
                while(next(pit)!=s.end()) {
                    auto ppit = next(pit);
                    if(ccw(p,*pit,*ppit)<=0) {
                        s.erase(pit);
                        pit = ppit;
                    } else break;
                }
                if(pit->Y>=p.Y) s.erase(pit);
            }
        }
    };
    vector<Hull> hs(n);
    struct el {
        int t,c;
        int at;
        ll cost() const {
            return ll(t)*c;
        }
        bool operator<(const el& o) const {
            return cost()>o.cost();
        }
    };
    priority_queue<el> pq;
    auto process = [&](int at, int t,int c) {
        if(!hs[at].inside({t,c})) {
            hs[at].insert({t,c});
            pq.push({t,c,at});
        }
    };
    process(0,0,0);
    vector<ll> ans(n,1e18);

    while(!pq.empty()) {
        auto e = pq.top(); pq.pop();
        ans[e.at] = min(ans[e.at],e.cost());
        if(hs[e.at].corner({e.t,e.c})) {
            for(auto [to,t,c] : adj[e.at]) {
                process(to,e.t+t,e.c+c);
            }
        }
    }
    for(auto& i : ans) {
        if(i==ll(1e18)) i=-1;
    }
    for(int i=1;i<n;++i) cout << ans[i] << '\n';

    
}

Compilation message

ceste.cpp: In member function 'void main()::Hull::insert(pt)':
ceste.cpp:59:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   59 |             auto [it,b] = s.insert(p);
      |                  ^
ceste.cpp: In function 'int main()':
ceste.cpp:110:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  110 |             for(auto [to,t,c] : adj[e.at]) {
      |                      ^

Subtask #1
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct

Subtask #2
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 340 KB Output is correct

Subtask #3
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct

Subtask #4
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 388 KB Output is correct

Subtask #5
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 568 KB Output is correct
2 Correct 3 ms 440 KB Output is correct
3 Correct 3 ms 340 KB Output is correct

Subtask #6
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 940 KB Output is correct
2 Correct 15 ms 820 KB Output is correct
3 Correct 7 ms 528 KB Output is correct

Subtask #7
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 253 ms 16968 KB Output is correct
2 Correct 176 ms 4436 KB Output is correct
3 Correct 4 ms 468 KB Output is correct

Subtask #8
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 1464 KB Output is correct
2 Correct 194 ms 8552 KB Output is correct
3 Correct 4 ms 724 KB Output is correct

Subtask #9
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 24 ms 2312 KB Output is correct
2 Correct 293 ms 16244 KB Output is correct
3 Correct 181 ms 11536 KB Output is correct

Subtask #10
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 273 ms 16484 KB Output is correct
2 Correct 219 ms 13216 KB Output is correct
3 Correct 314 ms 16552 KB Output is correct