Submission #1084365

#	Time	Username	Problem	Language	Result	Execution time	Memory
1084365		Equinox	Ceste (COCI17_ceste)	C++17	48 / 160	78 ms	8908 KiB

ceste

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<double,double> pdd;
typedef complex<double> cpx;
#define fastio cin.tie(0)->sync_with_stdio(0); cout.tie(0);
#define all(x) x.begin(),x.end()
#define compress(x) x.erase(unique(all(x)),x.end())
#define ff first
#define ss second

struct Edge{
    ll x,t,c;
};

struct Di{
    ll i,t,c,w;
    bool operator < (const Di &d) const {
        return w>d.w;
    }
};

ll n,m,dist[2010];
vector<Edge> g[2010];
vector<pll> h[2010];

ll ccw(pll a, pll b, pll c){
    ll k = (b.ff-a.ff)*(c.ss-a.ss)-(b.ss-a.ss)*(c.ff-a.ff);
    return (k>0)-(k<0);
}

void hull(ll id, pll p){
    ll n = (ll)h[id].size()+1, k = 0;
    h[id].push_back(p);
    if((ll)h[id].size()<3) return;
    if((ll)h[id].size()==3){
        if(ccw(h[id][0],h[id][1],h[id][2])<0) reverse(all(h[id]));
        return;
    }
    vector<pll> H(2*n+1);
    sort(all(h[id]));
    for(int i=0;i<n;i++){
        while(k>=0&&ccw(H[k-2],H[k-1],h[id][i])<=0) k--;
        H[k++] = h[id][i];
    }
    for(int i=n-1,t=k+1;i>0;i--){
        while(k>=t&&ccw(H[k-2],H[k-1],h[id][i-1])<=0) k--;
        H[k++] = h[id][i-1];
    }
    H.resize(k-1);
    h[id] = H;
}

ll inside(ll id, pll p){
    ll n = (ll)h[id].size();
    if(n<3) return 0;
    if(ccw(h[id][0],h[id][1],p)<0) return 0;
    if(ccw(h[id][0],h[id][n-1],p)>0) return 0;
    
    int l = 1, r = n-1;
    while(l+1<r){
        int m = (l+r)/2;
        if(ccw(h[id][0],h[id][m],p)>0) l = m;
        else r = m;
    }
    return ccw(h[id][l],p,h[id][l+1])<=0;
}

void dijkstra(){
    for(int i=1;i<=n;i++){
        dist[i] = (ll)1e18;
    }
    dist[1] = 0;
    h[1] = {{(ll)1e10,0},{0,0},{0,(ll)1e10}};
    priority_queue<Di> pq;
    pq.push({1,0,0,0});
    while(!pq.empty()){
        ll c = pq.top().i, ct = pq.top().t;
        ll cc = pq.top().c, cw = pq.top().w; pq.pop();
        //if(cw>dist[c]) continue;
        dist[c] = min(dist[c],cw);
        pll p = {ct,cc};
        if(inside(c,p)) continue;
        for(auto i:g[c]){
            ll nx = i.x, nc = cc+i.c, nt = ct+i.t;
            ll nw = nc*nt;
            pll np = {nc,nt};
            if(!inside(nx,np)&&dist[nx]>nw){
                pq.push({nx,nt,nc,nw});
            }
        }
    }
}

int main(){
    fastio;
    cin >> n >> m;
    for(int i=0;i<m;i++){
        ll x,y,z,w; cin >> x >> y >> z >> w;
        g[x].push_back({y,z,w});
        g[y].push_back({x,z,w});
    }
    dijkstra();
    for(int i=2;i<=n;i++){
        cout << (dist[i]<(ll)1e18?dist[i]:-1) << "\n";
    }
}

• Subtask 1: 16 / 16
• Subtask 2: 16 / 16
• Subtask 3: 0 / 16
• Subtask 4: 16 / 16
• Subtask 5: 0 / 16
• Subtask 6: 0 / 16
• Subtask 7: 0 / 16
• Subtask 8: 0 / 16
• Subtask 9: 0 / 16
• Subtask 10: 0 / 16