oj.uz

Submission #964760

# Submission time Handle Problem Language Result Execution time Memory
964760 2024-04-17T13:48:55 Z Aiperiii Evacuation plan (IZhO18_plan) C++14
10 / 100
 4000 ms 20468 KB 
#include <bits/stdc++.h>
#define int long long
#define ff first
#define ss second
#define pb push_back
#define all(x) x.begin(),x.end()
using namespace std;
const int N=1e5+5;
vector <pair <int,int > > g[N];
int no[N],d[N];
int find(int s,int n){
    set <pair <int,int> > st;
    st.insert({0,s});
    for(int i=1;i<=n;i++)d[i]=1e18;
    d[s]=0;
    while(!st.empty()){
        int v=st.begin()->ss;
        st.erase(st.begin());
        for(auto to : g[v]){
            if(d[to.ff]>d[v]+to.ss){
                st.erase({d[to.ff],to.ff});
                d[to.ff]=d[v]+to.ss;
                st.insert({d[to.ff],to.ff});
            }
        }
    }
    int mn=1e18;
    for(int i=1;i<=n;i++){
        if(no[i]){
            mn=min(mn,d[i]);
        }
    }
    if(mn==1e18)mn=0;
    return mn;
}
signed main(){
    ios_base::sync_with_stdio();
    cin.tie(0);cout.tie(0);
    int n,m;
    cin>>n>>m;
    for(int i=0;i<m;i++){
        int u,v,w;
        cin>>u>>v>>w;
        g[u].pb({v,w});
        g[v].pb({u,w});
    }
    int k;
    cin>>k;
    for(int i=0;i<k;i++){
        int x;
        cin>>x;
        no[x]=1;
    }
    int q;
    cin>>q;
    while(q--){
        int s,t;
        cin>>s>>t;
        cout<<min(find(s,n),find(t,n))<<"\n";
    }
}

/*
 
*/

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3928 KB Output is correct
2 Correct 277 ms 4300 KB Output is correct
3 Correct 296 ms 4300 KB Output is correct
4 Correct 2 ms 4180 KB Output is correct
5 Correct 272 ms 4188 KB Output is correct
6 Correct 264 ms 4432 KB Output is correct
7 Correct 2 ms 4188 KB Output is correct
8 Correct 2 ms 4180 KB Output is correct
9 Correct 257 ms 4244 KB Output is correct
10 Correct 270 ms 4244 KB Output is correct
11 Correct 253 ms 4248 KB Output is correct
12 Correct 264 ms 4300 KB Output is correct
13 Correct 259 ms 4444 KB Output is correct
14 Correct 273 ms 4184 KB Output is correct
15 Correct 273 ms 4440 KB Output is correct

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3928 KB Output is correct
2 Correct 277 ms 4300 KB Output is correct
3 Correct 296 ms 4300 KB Output is correct
4 Correct 2 ms 4180 KB Output is correct
5 Correct 272 ms 4188 KB Output is correct
6 Correct 264 ms 4432 KB Output is correct
7 Correct 2 ms 4188 KB Output is correct
8 Correct 2 ms 4180 KB Output is correct
9 Correct 257 ms 4244 KB Output is correct
10 Correct 270 ms 4244 KB Output is correct
11 Correct 253 ms 4248 KB Output is correct
12 Correct 264 ms 4300 KB Output is correct
13 Correct 259 ms 4444 KB Output is correct
14 Correct 273 ms 4184 KB Output is correct
15 Correct 273 ms 4440 KB Output is correct
16 Execution timed out 4103 ms 12676 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 3928 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 296 ms 20468 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3928 KB Output is correct
2 Correct 277 ms 4300 KB Output is correct
3 Correct 296 ms 4300 KB Output is correct
4 Correct 2 ms 4180 KB Output is correct
5 Correct 272 ms 4188 KB Output is correct
6 Correct 264 ms 4432 KB Output is correct
7 Correct 2 ms 4188 KB Output is correct
8 Correct 2 ms 4180 KB Output is correct
9 Correct 257 ms 4244 KB Output is correct
10 Correct 270 ms 4244 KB Output is correct
11 Correct 253 ms 4248 KB Output is correct
12 Correct 264 ms 4300 KB Output is correct
13 Correct 259 ms 4444 KB Output is correct
14 Correct 273 ms 4184 KB Output is correct
15 Correct 273 ms 4440 KB Output is correct
16 Execution timed out 4103 ms 12676 KB Time limit exceeded
17 Halted 0 ms 0 KB -