Submission #654924

#	Time	Username	Problem	Language	Result	Execution time	Memory
654924		jeroenodb	Ceste (COCI17_ceste)	C++14	160 / 160	314 ms	16968 KiB

ceste

#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 (stderr)

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 / 16
• Subtask 2: 16 / 16
• Subtask 3: 16 / 16
• Subtask 4: 16 / 16
• Subtask 5: 16 / 16
• Subtask 6: 16 / 16
• Subtask 7: 16 / 16
• Subtask 8: 16 / 16
• Subtask 9: 16 / 16
• Subtask 10: 16 / 16