oj.uz

Submission #1084639

# Submission time Handle Problem Language Result Execution time Memory
1084639 2024-09-06T15:21:27 Z Equinox Ceste (COCI17_ceste) C++17
160 / 160
 1404 ms 13600 KB 
#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 t){
    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;
    }
    if(t&&(p==h[id][l]||p==h[id][l+1])) return 0;
    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},{0,0}};
    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,1)) continue;
        for(auto i:g[c]){
            ll nx = i.x, nc = cc+i.c, nt = ct+i.t;
            ll nw = nc*nt;
            pll np = {nt,nc};
            if(!inside(nx,np,0)){
                //cout << nx << " " << h[nx].size() << " " << nt << " " << nc << "\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
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 860 KB Output is correct
2 Correct 2 ms 856 KB Output is correct
3 Correct 1 ms 604 KB Output is correct

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 1496 KB Output is correct
2 Correct 26 ms 1508 KB Output is correct
3 Correct 6 ms 856 KB Output is correct

Subtask #7
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 989 ms 13524 KB Output is correct
2 Correct 483 ms 8644 KB Output is correct
3 Correct 2 ms 856 KB Output is correct

Subtask #8
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 1540 KB Output is correct
2 Correct 583 ms 10224 KB Output is correct
3 Correct 3 ms 860 KB Output is correct

Subtask #9
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 2540 KB Output is correct
2 Correct 1057 ms 13600 KB Output is correct
3 Correct 622 ms 9516 KB Output is correct

Subtask #10
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1000 ms 13264 KB Output is correct
2 Correct 800 ms 11024 KB Output is correct
3 Correct 1404 ms 13504 KB Output is correct