oj.uz

Submission #945913

# Submission time Handle Problem Language Result Execution time Memory
945913 2024-03-14T08:41:50 Z ezzzay Commuter Pass (JOI18_commuter_pass) C++14
31 / 100
 292 ms 31936 KB 
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ff first
#define ss second
#define pb push_back
const int N=3e5+5;
vector<pair<int,int>>v[N];
int n,m,s,t,x,y;
int dist[N];
int tmp[N];
int par[N];
int d[500][500];
bool vis[N];
vector<pair<int,int>>vc;
void dfs(int a){
    vis[a]=1;
    for(auto p:v[a]){
        int b=p.ff;
        int c=p.ss;
        if(vis[b]==0 and dist[b]+c==dist[a])dfs(b);
    }
}
void sbtsk1(){
    for(int i=0;i<m;i++){
        int a,b,c;
        cin>>a>>b>>c;
        v[a].pb({b,c});
        v[b].pb({a,c});
    }
    for(int i=1;i<=n;i++){
        dist[i]=1e16;
    }
    priority_queue<pair<int,int>>q;
    q.push({0,s});
    par[s]=s;
    dist[s]=0;
    vis[s]=1;
    while(!q.empty()){
        int w=-q.top().ff;
        int a=q.top().ss;
        q.pop();
        if(dist[a]<w)continue;
        for(auto p:v[a]){
            
            int b=p.ff;
            int c=p.ss;
            if(dist[a]+c<dist[b]){
               
                dist[b]=dist[a]+c;
                par[b]=a;
                q.push({-dist[b],b});
            }
        }
    }
    
    dfs(t);
    for(int i=1;i<=n;i++){
        dist[i]=1e16;
    }
    s=y;
    q.push({0,s});
    dist[s]=0;
    while(!q.empty()){
        int w=-q.top().ff;
        int a=q.top().ss;
        q.pop();
        if(dist[a]<w)continue;
        for(auto p:v[a]){
            int b=p.ff;
            int c=p.ss;
            if(dist[a]+c<dist[b]){
                dist[b]=dist[a]+c;
                par[b]=a;
                q.push({-dist[b],b});
            }
        }
    }
    int ans=1e16;
    for(int i=1;i<=n;i++){
        if(vis[i]){
           
            ans=min(ans,dist[i]);
        }
    }
    cout<<ans;
}
void sbtsk2(){
    for(int i=0;i<m;i++){
        int a,b,c;
        cin>>a>>b>>c;
        v[a].pb({b,c});
        v[b].pb({a,c});
    }
    for(int i=1;i<=n;i++){
        dist[i]=1e16;
    }
    priority_queue<pair<int,int>>q;
    q.push({0,s});
    par[s]=s;
    dist[s]=0;
    while(!q.empty()){
        int w=-q.top().ff;
        int a=q.top().ss;
        q.pop();
        if(dist[a]<w)continue;
        for(auto p:v[a]){
            int b=p.ff;
            int c=p.ss;
            if(dist[a]+c<dist[b]){
                dist[b]=dist[a]+c;
                par[b]=a;
                q.push({-dist[b],b});
            }
        }
    }
    while(t!=s){
        v[t].pb({par[t],0});
        v[par[t]].pb({t,0});
        t=par[t];
    }
    for(int i=1;i<=n;i++){
        dist[i]=1e16;
    }
    s=x;
    q.push({0,s});
    par[s]=s;
    dist[s]=0;
    while(!q.empty()){
        int w=-q.top().ff;
        int a=q.top().ss;
        q.pop();
        if(dist[a]<w)continue;
        for(auto p:v[a]){
            int b=p.ff;
            int c=p.ss;
            if(dist[a]+c<dist[b]){
                dist[b]=dist[a]+c;
                par[b]=a;
                q.push({-dist[b],b});
            }
        }
    }
    cout<<dist[y];
}
void subtsk3(){
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(i==j){
                d[i][j]=0;
                continue;
            }
            d[i][j]=1e14;
        }
    }
    for(int i=0;i<m;i++){
        int a,b,c;
        cin>>a>>b>>c;
        d[a][b]=min(d[a][b],c);
        d[b][a]=min(d[b][a],c);
    }
    for(int k=1;k<=n;k++){
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                if(d[i][j]> d[i][k]+d[k][j]){
                    d[i][j]=d[i][k]+d[k][j];
                }
            }
        }
    }
    
    int ans=1e14;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(d[s][i]+d[i][j]+d[j][t]==d[s][t]){
                ans=min(ans,d[x][i]+d[j][y]);
                ans=min(ans,d[x][j]+d[i][y]);
                
                ans=min(ans,d[y][i]+d[j][x]);
                ans=min(ans,d[y][j]+d[i][x]);
            }
            
        }
    }
    cout<<ans;
}
signed main(){
    cin>>n>>m>>s>>t>>x>>y;
     if(n<=300){
        subtsk3();
        return 0;
    }
    if(s==x){
        sbtsk1();
        return 0;
    }
   
    sbtsk2();
}

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 290 ms 24828 KB Output is correct
2 Correct 262 ms 24044 KB Output is correct
3 Correct 230 ms 26820 KB Output is correct
4 Correct 208 ms 25052 KB Output is correct
5 Correct 201 ms 24012 KB Output is correct
6 Correct 228 ms 24784 KB Output is correct
7 Correct 220 ms 23928 KB Output is correct
8 Correct 213 ms 24008 KB Output is correct
9 Correct 212 ms 24084 KB Output is correct
10 Correct 235 ms 23872 KB Output is correct
11 Correct 93 ms 19560 KB Output is correct
12 Correct 226 ms 24012 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 253 ms 26576 KB Output is correct
2 Correct 222 ms 26716 KB Output is correct
3 Correct 227 ms 26448 KB Output is correct
4 Correct 230 ms 26888 KB Output is correct
5 Correct 292 ms 27088 KB Output is correct
6 Correct 242 ms 29100 KB Output is correct
7 Correct 247 ms 31936 KB Output is correct
8 Correct 234 ms 26704 KB Output is correct
9 Correct 262 ms 27292 KB Output is correct
10 Correct 225 ms 26568 KB Output is correct
11 Correct 109 ms 21200 KB Output is correct
12 Correct 258 ms 28372 KB Output is correct

Subtask #3
0 / 24.0

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

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 290 ms 24828 KB Output is correct
2 Correct 262 ms 24044 KB Output is correct
3 Correct 230 ms 26820 KB Output is correct
4 Correct 208 ms 25052 KB Output is correct
5 Correct 201 ms 24012 KB Output is correct
6 Correct 228 ms 24784 KB Output is correct
7 Correct 220 ms 23928 KB Output is correct
8 Correct 213 ms 24008 KB Output is correct
9 Correct 212 ms 24084 KB Output is correct
10 Correct 235 ms 23872 KB Output is correct
11 Correct 93 ms 19560 KB Output is correct
12 Correct 226 ms 24012 KB Output is correct
13 Correct 253 ms 26576 KB Output is correct
14 Correct 222 ms 26716 KB Output is correct
15 Correct 227 ms 26448 KB Output is correct
16 Correct 230 ms 26888 KB Output is correct
17 Correct 292 ms 27088 KB Output is correct
18 Correct 242 ms 29100 KB Output is correct
19 Correct 247 ms 31936 KB Output is correct
20 Correct 234 ms 26704 KB Output is correct
21 Correct 262 ms 27292 KB Output is correct
22 Correct 225 ms 26568 KB Output is correct
23 Correct 109 ms 21200 KB Output is correct
24 Correct 258 ms 28372 KB Output is correct
25 Correct 46 ms 10328 KB Output is correct
26 Incorrect 31 ms 10332 KB Output isn't correct
27 Halted 0 ms 0 KB -