oj.uz

Submission #1084365

# Submission time Handle Problem Language Result Execution time Memory
1084365 2024-09-06T05:12:26 Z Equinox Ceste (COCI17_ceste) C++17
48 / 160
 78 ms 8908 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);
}

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.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 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
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
16.0 / 16.0

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

Subtask #5
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Incorrect 1 ms 604 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 1748 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 1756 KB Output is correct
2 Incorrect 59 ms 8908 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 860 KB Output is correct
2 Incorrect 52 ms 4984 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #9
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 2880 KB Output is correct
2 Correct 67 ms 2772 KB Output is correct
3 Incorrect 30 ms 1756 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #10
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 2768 KB Output is correct
2 Incorrect 43 ms 2776 KB Output isn't correct
3 Halted 0 ms 0 KB -