oj.uz

Submission #341294

# Submission time Handle Problem Language Result Execution time Memory
341294 2020-12-29T11:24:27 Z bigDuck Commuter Pass (JOI18_commuter_pass) C++14
100 / 100
 906 ms 32092 KB 
#include<bits/stdc++.h>
using namespace std;
#define INIT  ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define mp make_pair
#define pb push_back
#define ft first
#define sc second
#define ll long long
#define pii pair<int, int>
#define count_bits __builtin_popcount
#define int ll

int n, m, S, T, U, V;


int Ds[100010], Du[100010], Dt[100010], Dv[100010];
bool v[100010];

vector<pii> g[100010];
pair<int ,pii> e[200010];


vector<pii> g2[100010];


void dijkstra(int s, vector<pii> g[], int D[], bool v[]){
    multiset<pii> ms;
    ms.insert({0, s});
    D[s]=0;

    while(!ms.empty()){
        pii pr=(*ms.begin()); ms.erase(ms.begin());
        int node=pr.sc, d=pr.ft;
        v[node]=true;
        for(pii pr:g[node]){
            int u=pr.ft, c=pr.sc;
            if(!v[u]){
                auto it=ms.find({D[u], u});
                if(it==ms.end()){
                    D[u]=d+c;
                    ms.insert({D[u], u});
                }
                else{
                    if((d+c)<D[u]){
                        D[u]=d+c;
                        ms.erase(it);
                        ms.insert({D[u], u});
                    }
                }
            }
        }
    }
for(int i=1; i<=n;i++){
    v[i]=false;
}

}


void build_g2(){

for(int i=1; i<=m; i++){
    int u=e[i].sc.ft, v=e[i].sc.sc, c=e[i].ft;
    if( (Ds[u]+c+Dt[v])==Ds[T]  ){
        g2[u].pb({v, c});
    }
    if( (Ds[v]+c+Dt[u])==Ds[T] ){
        g2[v].pb({u, c});
    }
}

}

int res=1e18;
int mnu[100010], mnv[100010];




int dfsu(int s){

    int dv=Dv[s];
    v[s]=true;
    for(pii pr:g2[s]){
        int u=pr.ft;
        dv=min(dv, Dv[u]);
        if(!v[u]){
        dv=min(dfsu(u), dv);}
        dv=min(dv, mnv[u]);
    }
    res=min(res, Du[s]+dv);
    mnv[s]=dv;
    return dv;
}

int dfsv(int s){

    int du=Du[s];
    v[s]=true;
    for(pii pr:g2[s]){
        int u=pr.ft;
        du=min(du, Du[u]);
        if(!v[u]){
        du=min(dfsv(u), du);}
        du=min(du, mnu[u]);
    }
    res=min(res, du+Dv[s]);
    mnu[s]=du;
    return du;
}



int32_t main(){
INIT
cin>>n>>m;
cin>>S>>T;
cin>>U>>V;

for(int i=1; i<=m; i++){
    int u, v, c;
    cin>>u>>v>>c;
    g[u].pb({v, c});
    g[v].pb({u, c});
    e[i]={c, {u, v}};
}

dijkstra(S, g, Ds, v);
dijkstra(T, g, Dt, v);
dijkstra(U, g, Du, v);
dijkstra(V, g, Dv, v);
build_g2();



dfsu(S);
for(int i=1; i<=n; i++){
    v[i]=false;
}

dfsv(S);







cout<<min(res, Du[V]);

return 0;
}

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 741 ms 26476 KB Output is correct
2 Correct 634 ms 26988 KB Output is correct
3 Correct 630 ms 32092 KB Output is correct
4 Correct 753 ms 26604 KB Output is correct
5 Correct 617 ms 27244 KB Output is correct
6 Correct 797 ms 26732 KB Output is correct
7 Correct 645 ms 27124 KB Output is correct
8 Correct 629 ms 27244 KB Output is correct
9 Correct 668 ms 25484 KB Output is correct
10 Correct 581 ms 25708 KB Output is correct
11 Correct 191 ms 21740 KB Output is correct
12 Correct 674 ms 25324 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 744 ms 29604 KB Output is correct
2 Correct 656 ms 29292 KB Output is correct
3 Correct 660 ms 28780 KB Output is correct
4 Correct 642 ms 29036 KB Output is correct
5 Correct 674 ms 29676 KB Output is correct
6 Correct 635 ms 31596 KB Output is correct
7 Correct 681 ms 31852 KB Output is correct
8 Correct 674 ms 29164 KB Output is correct
9 Correct 686 ms 29676 KB Output is correct
10 Correct 668 ms 28780 KB Output is correct
11 Correct 221 ms 24044 KB Output is correct
12 Correct 602 ms 31852 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 7148 KB Output is correct
2 Correct 4 ms 5100 KB Output is correct
3 Correct 4 ms 5100 KB Output is correct
4 Correct 32 ms 8812 KB Output is correct
5 Correct 17 ms 6892 KB Output is correct
6 Correct 4 ms 5228 KB Output is correct
7 Correct 5 ms 5228 KB Output is correct
8 Correct 6 ms 5356 KB Output is correct
9 Correct 5 ms 5228 KB Output is correct
10 Correct 17 ms 7020 KB Output is correct
11 Correct 3 ms 5100 KB Output is correct
12 Correct 4 ms 5100 KB Output is correct
13 Correct 4 ms 5100 KB Output is correct
14 Correct 4 ms 5228 KB Output is correct
15 Correct 4 ms 5228 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 741 ms 26476 KB Output is correct
2 Correct 634 ms 26988 KB Output is correct
3 Correct 630 ms 32092 KB Output is correct
4 Correct 753 ms 26604 KB Output is correct
5 Correct 617 ms 27244 KB Output is correct
6 Correct 797 ms 26732 KB Output is correct
7 Correct 645 ms 27124 KB Output is correct
8 Correct 629 ms 27244 KB Output is correct
9 Correct 668 ms 25484 KB Output is correct
10 Correct 581 ms 25708 KB Output is correct
11 Correct 191 ms 21740 KB Output is correct
12 Correct 674 ms 25324 KB Output is correct
13 Correct 744 ms 29604 KB Output is correct
14 Correct 656 ms 29292 KB Output is correct
15 Correct 660 ms 28780 KB Output is correct
16 Correct 642 ms 29036 KB Output is correct
17 Correct 674 ms 29676 KB Output is correct
18 Correct 635 ms 31596 KB Output is correct
19 Correct 681 ms 31852 KB Output is correct
20 Correct 674 ms 29164 KB Output is correct
21 Correct 686 ms 29676 KB Output is correct
22 Correct 668 ms 28780 KB Output is correct
23 Correct 221 ms 24044 KB Output is correct
24 Correct 602 ms 31852 KB Output is correct
25 Correct 18 ms 7148 KB Output is correct
26 Correct 4 ms 5100 KB Output is correct
27 Correct 4 ms 5100 KB Output is correct
28 Correct 32 ms 8812 KB Output is correct
29 Correct 17 ms 6892 KB Output is correct
30 Correct 4 ms 5228 KB Output is correct
31 Correct 5 ms 5228 KB Output is correct
32 Correct 6 ms 5356 KB Output is correct
33 Correct 5 ms 5228 KB Output is correct
34 Correct 17 ms 7020 KB Output is correct
35 Correct 3 ms 5100 KB Output is correct
36 Correct 4 ms 5100 KB Output is correct
37 Correct 4 ms 5100 KB Output is correct
38 Correct 4 ms 5228 KB Output is correct
39 Correct 4 ms 5228 KB Output is correct
40 Correct 906 ms 28508 KB Output is correct
41 Correct 733 ms 25724 KB Output is correct
42 Correct 717 ms 25836 KB Output is correct
43 Correct 237 ms 24300 KB Output is correct
44 Correct 230 ms 24172 KB Output is correct
45 Correct 620 ms 29540 KB Output is correct
46 Correct 604 ms 29420 KB Output is correct
47 Correct 758 ms 27132 KB Output is correct
48 Correct 248 ms 21740 KB Output is correct
49 Correct 798 ms 28640 KB Output is correct
50 Correct 616 ms 28268 KB Output is correct
51 Correct 592 ms 29420 KB Output is correct