Submission #1084366

#	Time	Username	Problem	Language	Result	Execution time	Memory
1084366		Equinox	Ceste (COCI17_ceste)	C++17	0 / 160	15 ms	1624 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);
}

vector<pll> convexhull(vector<pll> &p){
    ll n = p.size(),k=0;
    if(n<3) return p;
    if(n==3){
        if(ccw(p[0],p[1],p[2])<0) reverse(all(p));
        return p;
    }
    vector<pll> H(2*n);
    sort(all(p));
    for(int i=0;i<n;i++){
        while(k>=2&&ccw(H[k-2],H[k-1],p[i])<=0) k--;
        H[k++] = p[i];
    }
    for(int i=n-1,t=k+1;i>0;i--){
        while(k>=t&&ccw(H[k-2],H[k-1],p[i-1])<=0) k--;
        H[k++] = p[i-1];
    }
    H.resize(k-1);
    return 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;
    }
    for(int i=2;i<=n;i++){
        h[i] = {{(ll)1e8,0},{0,(ll)1e8}};
    }
    dist[1] = 0;
    h[1] = {{(ll)1e8,0},{0,(ll)1e8}};
    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();
        //cout << c << "\n";
        //if(cw>dist[c]) continue;
        dist[c] = min(dist[c],cw);
        pll p = {ct,cc};
        if(inside(c,p)) continue;
        if(c==1) h[c].push_back({0,0});
        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)){
                //cout << nx << " " << h[nx].size() << " " << nc << " " << nt << "\n";
                h[nx].push_back(np);
                h[nx] = convexhull(h[nx]);
                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: 0 / 16
• Subtask 2: 0 / 16
• Subtask 3: 0 / 16
• Subtask 4: 0 / 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