oj.uz

Submission #259311

# Submission time Handle Problem Language Result Execution time Memory
259311 2020-08-07T14:26:12 Z Fidisk Commuter Pass (JOI18_commuter_pass) C++14
15 / 100
 2000 ms 32384 KB 
#include <bits/stdc++.h>
using namespace std;

#define oo 1e18
#define fi first
#define se second
#define sp(iiii) setprecision(iiii)
#define IO ios_base::sync_with_stdio(false); cin.tie(0)
#define ms(aaaa,xxxx) memset(aaaa,xxxx,sizeof(aaaa))
#define cntbit(xxxx) __builtin_popcount(xxxx)
#define getbit(xxxx,aaaa) ((xxxx>>(aaaa-1))&1)
#define _cos(xxxx) cos(xxxx*acos(-1)/180)
#define _sin(xxxx) sin(xxxx*acos(-1)/180)
#define _tan(xxxx) tan(xxxx*acos(-1)/180)
#define PE cout<<fixed

typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<pair<int,int>,int> piii;
typedef pair<long long,long long> pll;
typedef pair<pair<long long,long long>,long long> plll;

const ld pi=acos(-1);

struct comp{
    bool operator() (pll x,pll y) {
        return x.se>y.se;
    }
};

ll n,m,s,t,u,v,a,b,c,res,f[5][500009],i;
priority_queue<pll,vector<pll>,comp> heap;
vector<pll> g[500009];
pll tmp;

void Dijsktra(ll x,ll y){
    heap.push({y,y-y});
    for (int ii=1;ii<=n;ii++) {
        f[x][ii]=oo;
    }
    f[x][y]=0;
    while (!heap.empty()) {
        tmp=heap.top();
        heap.pop();
        if (f[x][tmp.fi]<tmp.se) {
            
        } 
        else {
            for (int ii=0;ii<g[tmp.fi].size();ii++) {
                if (f[x][g[tmp.fi][ii].fi]>tmp.se+g[tmp.fi][ii].se) {
                    f[x][g[tmp.fi][ii].fi]=tmp.se+g[tmp.fi][ii].se;
                    heap.push({g[tmp.fi][ii].fi,tmp.se+g[tmp.fi][ii].se});
                }
            }
        }
    }
}

pll calc(pll x,pll y) {
    return {min(x.fi,y.fi),min(x.se,y.se)};
}

pll Trace(ll x) {
    //cout<<x<<'\n';
    pll kq={f[2][x],f[3][x]};
    for (int ii=0;ii<g[x].size();ii++) {
        if ((f[1][g[x][ii].fi]==f[1][x]-g[x][ii].se)) {
            pll tmp3=Trace(g[x][ii].fi);
            kq=calc(kq,tmp3);
        }
    }
    return kq;
}

int main(){
    IO;
    cin>>n>>m;
    cin>>s>>t;
    cin>>u>>v;
    for (i=1;i<=m;i++) {
        cin>>a>>b>>c;
        g[a].push_back({b,c});
        g[b].push_back({a,c});
    }
    Dijsktra(1,s);
    Dijsktra(2,u);
    Dijsktra(3,v);
    res=f[2][v];
    pll tmp2=Trace(t);
    //cout<<tmp2.fi<<' '<<tmp2.se<<'\n';
    res=min(tmp2.fi+tmp2.se,res);
    cout<<res;
}

Compilation message

commuter_pass.cpp: In function 'void Dijsktra(ll, ll)':
commuter_pass.cpp:51:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (int ii=0;ii<g[tmp.fi].size();ii++) {
                           ~~^~~~~~~~~~~~~~~~~
commuter_pass.cpp: In function 'pll Trace(ll)':
commuter_pass.cpp:68:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int ii=0;ii<g[x].size();ii++) {
                   ~~^~~~~~~~~~~~

Subtask #1
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 381 ms 30052 KB Output is correct
2 Execution timed out 2086 ms 29740 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 360 ms 30952 KB Output is correct
2 Correct 354 ms 31024 KB Output is correct
3 Correct 362 ms 30552 KB Output is correct
4 Correct 367 ms 30960 KB Output is correct
5 Correct 306 ms 31216 KB Output is correct
6 Correct 336 ms 32304 KB Output is correct
7 Correct 351 ms 32364 KB Output is correct
8 Correct 361 ms 31016 KB Output is correct
9 Correct 353 ms 31124 KB Output is correct
10 Correct 390 ms 30576 KB Output is correct
11 Correct 208 ms 24720 KB Output is correct
12 Correct 374 ms 32384 KB Output is correct

Subtask #3
0 / 24.0

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

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 381 ms 30052 KB Output is correct
2 Execution timed out 2086 ms 29740 KB Time limit exceeded
3 Halted 0 ms 0 KB -