oj.uz

Submission #1084344

# Submission time Handle Problem Language Result Execution time Memory
1084344 2024-09-06T02:52:19 Z Equinox Ceste (COCI17_ceste) C++17
0 / 160
 2500 ms 131072 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;
};

ll n,m,dist[2010];
pll dsum[2010];
vector<Edge> g[2010];
map<pll,pll> mp;
ll ans[2010];

pll dijkstra(ll x, ll a, ll b){
    for(int i=1;i<=n;i++){
        dist[i] = (ll)1e15;
        dsum[i] = {(ll)1e15,(ll)1e15};
    }
    dist[1] = 0;
    dsum[1] = {0,0};
    priority_queue<pair<pll,pll> > pq;
    pq.push({{0,1},{0,0}});
    while(!pq.empty()){
        ll c = pq.top().ff.ss, w = -pq.top().ff.ff;
        ll ca = pq.top().ss.ff, cb = pq.top().ss.ss;
        pq.pop();
        if(dist[c]<w) continue;
        for(auto i:g[c]){
            ll nx = i.x, nw = w + a*i.t + b*i.c;
            ll na = ca + i.t, nb = cb + i.c;
            if(nw<dist[nx]){
                dist[nx] = nw;
                dsum[nx] = {na,nb};
                //cout << i.x << " " << c << " " << nx << "\n";
                pq.push({{-dist[nx],nx},{na,nb}});
            }
        }
    }
    for(int i=2;i<=n;i++){
        ans[i] = min(ans[i],dsum[i].ff*dsum[i].ss);
        mp[{a,b}] = dsum[i];
    }
    if(dist[x]>(ll)1e14) return dsum[x];
    else{
        return dsum[x];
    }
}

void qhull(ll x, pll a, pll b){
    ll ta = a.ss-b.ss, tb = b.ff-a.ff;
    pll c = mp[{ta,tb}];
    if(c.ff==0&&c.ss==0) c = dijkstra(x,a.ss-b.ss,b.ff-a.ff);
    if((b.ff-a.ff)*(c.ss-a.ss)==(b.ss-a.ss)*(c.ff-a.ff)) return;
    qhull(x,a,c); qhull(x,c,b);
}

ll solve(ll x){
    pll lc = dijkstra(x,1,0);
    pll rc = dijkstra(x,0,1);
    // cout << lc.ff << " " << lc.ss << "\n";
    // cout << rc.ff << " " << rc.ss << "\n";
    if(lc.ff>(ll)1e14) return -1;
    qhull(x,lc,rc);
    return ans[x];
}

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});
    }
    for(int i=2;i<=n;i++){
        ans[i] = (ll)1e18;
    }
    for(int i=2;i<=n;i++){
        cout << solve(i) << "\n";
    }
}

Subtask #1
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 199 ms 131072 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2576 ms 764 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 205 ms 131072 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 180 ms 131072 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #5
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 236 ms 131072 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #6
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 150 ms 131072 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #7
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 645 ms 131072 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 269 ms 131072 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #9
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 224 ms 131072 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #10
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 293 ms 131072 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -