oj.uz

Submission #1084340

# Submission time Handle Problem Language Result Execution time Memory
1084340 2024-09-06T01:51:18 Z Equinox Ceste (COCI17_ceste) C++17
96 / 160
 2500 ms 724 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];

ll ans = (ll)1e15;

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}});
            }
        }
    }
    if(dist[x]>(ll)1e14) return dsum[x];
    else{
        ans = min(ans,dsum[x].ff*dsum[x].ss);
        return dsum[x];
    }
}

void qhull(ll x, pll a, pll b){
    pll 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){
    ans = (ll)1e18;
    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;
}

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++){
        cout << solve(i) << "\n";
    }
}

Subtask #1
16.0 / 16.0

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

Subtask #2
16.0 / 16.0

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

Subtask #3
16.0 / 16.0

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

Subtask #4
16.0 / 16.0

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

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 396 ms 656 KB Output is correct
2 Correct 177 ms 652 KB Output is correct
3 Correct 25 ms 600 KB Output is correct

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 322 ms 544 KB Output is correct
2 Correct 186 ms 596 KB Output is correct
3 Correct 108 ms 600 KB Output is correct

Subtask #7
0 / 16.0

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

Subtask #8
0 / 16.0

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

Subtask #9
0 / 16.0

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

Subtask #10
0 / 16.0

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