oj.uz

Submission #964763

# Submission time Handle Problem Language Result Execution time Memory
964763 2024-04-17T13:54:02 Z Aiperiii Evacuation plan (IZhO18_plan) C++14
23 / 100
 626 ms 42188 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;
        g[0].pb({x,0});
        g[x].pb({0,0});
    }
    find(0,n);
    for(int i=1;i<=n;i++){
        if(d[i]==1e18)d[i]=0;
    }
    int q;
    cin>>q;
    while(q--){
        int s,t;
        cin>>s>>t;
        cout<<min(d[s],d[t])<<"\n";
    }
}

/*
9 12
1 9 4
1 2 5
2 3 7
2 4 3
4 3 6
3 6 4
8 7 10
6 7 5
5 8 1
9 5 7
5 4 12
6 8 2
2
4 7
*/

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4340 KB Output is correct
2 Correct 3 ms 4192 KB Output is correct
3 Correct 3 ms 4188 KB Output is correct
4 Correct 2 ms 4176 KB Output is correct
5 Correct 3 ms 4312 KB Output is correct
6 Correct 3 ms 4188 KB Output is correct
7 Correct 2 ms 4184 KB Output is correct
8 Correct 2 ms 4188 KB Output is correct
9 Correct 3 ms 4188 KB Output is correct
10 Correct 2 ms 4188 KB Output is correct
11 Correct 2 ms 4188 KB Output is correct
12 Correct 3 ms 4188 KB Output is correct
13 Correct 2 ms 4188 KB Output is correct
14 Correct 2 ms 4188 KB Output is correct
15 Correct 2 ms 4188 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4340 KB Output is correct
2 Correct 3 ms 4192 KB Output is correct
3 Correct 3 ms 4188 KB Output is correct
4 Correct 2 ms 4176 KB Output is correct
5 Correct 3 ms 4312 KB Output is correct
6 Correct 3 ms 4188 KB Output is correct
7 Correct 2 ms 4184 KB Output is correct
8 Correct 2 ms 4188 KB Output is correct
9 Correct 3 ms 4188 KB Output is correct
10 Correct 2 ms 4188 KB Output is correct
11 Correct 2 ms 4188 KB Output is correct
12 Correct 3 ms 4188 KB Output is correct
13 Correct 2 ms 4188 KB Output is correct
14 Correct 2 ms 4188 KB Output is correct
15 Correct 2 ms 4188 KB Output is correct
16 Correct 141 ms 13964 KB Output is correct
17 Correct 626 ms 41904 KB Output is correct
18 Correct 37 ms 7432 KB Output is correct
19 Correct 158 ms 18436 KB Output is correct
20 Correct 597 ms 41904 KB Output is correct
21 Correct 287 ms 25204 KB Output is correct
22 Correct 124 ms 12692 KB Output is correct
23 Correct 620 ms 41888 KB Output is correct
24 Correct 567 ms 41808 KB Output is correct
25 Correct 598 ms 42188 KB Output is correct
26 Correct 159 ms 18400 KB Output is correct
27 Correct 169 ms 18488 KB Output is correct
28 Correct 146 ms 18700 KB Output is correct
29 Correct 142 ms 18368 KB Output is correct
30 Correct 155 ms 18364 KB Output is correct

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 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 216 ms 20048 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4340 KB Output is correct
2 Correct 3 ms 4192 KB Output is correct
3 Correct 3 ms 4188 KB Output is correct
4 Correct 2 ms 4176 KB Output is correct
5 Correct 3 ms 4312 KB Output is correct
6 Correct 3 ms 4188 KB Output is correct
7 Correct 2 ms 4184 KB Output is correct
8 Correct 2 ms 4188 KB Output is correct
9 Correct 3 ms 4188 KB Output is correct
10 Correct 2 ms 4188 KB Output is correct
11 Correct 2 ms 4188 KB Output is correct
12 Correct 3 ms 4188 KB Output is correct
13 Correct 2 ms 4188 KB Output is correct
14 Correct 2 ms 4188 KB Output is correct
15 Correct 2 ms 4188 KB Output is correct
16 Correct 141 ms 13964 KB Output is correct
17 Correct 626 ms 41904 KB Output is correct
18 Correct 37 ms 7432 KB Output is correct
19 Correct 158 ms 18436 KB Output is correct
20 Correct 597 ms 41904 KB Output is correct
21 Correct 287 ms 25204 KB Output is correct
22 Correct 124 ms 12692 KB Output is correct
23 Correct 620 ms 41888 KB Output is correct
24 Correct 567 ms 41808 KB Output is correct
25 Correct 598 ms 42188 KB Output is correct
26 Correct 159 ms 18400 KB Output is correct
27 Correct 169 ms 18488 KB Output is correct
28 Correct 146 ms 18700 KB Output is correct
29 Correct 142 ms 18368 KB Output is correct
30 Correct 155 ms 18364 KB Output is correct
31 Incorrect 1 ms 3928 KB Output isn't correct
32 Halted 0 ms 0 KB -