oj.uz

Submission #985241

# Submission time Handle Problem Language Result Execution time Memory
985241 2024-05-17T13:43:05 Z Aiperiii Swapping Cities (APIO20_swap) C++14
0 / 100
 2000 ms 25668 KB 
#include <bits/stdc++.h>
//#include "swap.h"
#define ff first
#define ss second
#define pb push_back
#define all(x) x.begin(),x.end()
using namespace std;
const int N=1e3+5;
vector <pair <int,int> > g[N];
int d[N][N];
int n;
void init(int N, int M,vector<int> U,vector<int> V,vector<int> W) {
    n=N;
    for(int i=0;i<M;i++){
        g[V[i]].pb({U[i],W[i]});
        g[U[i]].pb({V[i],W[i]});
    }
}

int getMinimumFuelCapacity(int X, int Y) {
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            d[i][j]=1e9+5;
        }
    }
    d[X][Y]=0;
    set <pair <int,pair <int,int> > > st;
    st.insert({0,{X,Y}});
    while(!st.empty()){
        int a=st.begin()->ss.ff,b=st.begin()->ss.ss;
        st.erase(st.begin());
        for(auto to : g[a]){
            if(to.ff!=b){
                if(d[to.ff][b]>max(d[a][b],to.ss)){
                    st.erase({d[to.ff][b],{to.ff,b}});
                    d[to.ff][b]=max(d[a][b],to.ss);
                    st.insert({d[to.ff][b],{to.ff,b}});
                }
            }
        }
        for(auto to : g[b]){
            if(to.ff!=a){
                if(d[a][to.ff]>max(d[a][b],to.ss)){
                    st.erase({d[a][to.ff],{a,to.ff}});
                    d[a][to.ff]=max(d[a][b],to.ss);
                    st.insert({d[a][to.ff],{a,to.ff}});
                }
            }
        }
    }
    if(d[Y][X]==1e9+5)d[Y][X]=-1;
    return d[Y][X];
}

/*signed main(){
    ios_base::sync_with_stdio();
    cin.tie(0);cout.tie(0);
    int n,m;
    cin>>n>>m;
    vector <int> a(m),b(m),c(m);
    for(int i=0;i<m;i++){
        cin>>a[i]>>b[i]>>c[i];
    }
    init(n,m,a,b,c);
    int q;
    cin>>q;
    while(q--){
        int u,v;
        cin>>u>>v;
        cout<<getMinimumFuelCapacity(u,v)<<"\n";
    }
}*/
/*
 3
 1 10
 3 10
 8 15
 
2
1 2
2 3
*/

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 504 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 69 ms 3924 KB Output is correct
5 Correct 298 ms 10872 KB Output is correct
6 Correct 355 ms 8868 KB Output is correct
7 Correct 414 ms 13172 KB Output is correct
8 Correct 375 ms 7880 KB Output is correct
9 Runtime error 19 ms 4188 KB Execution killed with signal 11
10 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 504 KB Output is correct
3 Runtime error 48 ms 8020 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 504 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 69 ms 3924 KB Output is correct
5 Correct 298 ms 10872 KB Output is correct
6 Correct 355 ms 8868 KB Output is correct
7 Correct 414 ms 13172 KB Output is correct
8 Correct 375 ms 7880 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 879 ms 22132 KB Output is correct
11 Correct 885 ms 14048 KB Output is correct
12 Correct 852 ms 17752 KB Output is correct
13 Correct 670 ms 16940 KB Output is correct
14 Correct 766 ms 8004 KB Output is correct
15 Correct 885 ms 8428 KB Output is correct
16 Correct 847 ms 9276 KB Output is correct
17 Correct 857 ms 10688 KB Output is correct
18 Correct 1071 ms 25668 KB Output is correct
19 Correct 730 ms 15272 KB Output is correct
20 Correct 941 ms 14396 KB Output is correct
21 Execution timed out 2008 ms 23272 KB Time limit exceeded
22 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 504 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 69 ms 3924 KB Output is correct
6 Correct 298 ms 10872 KB Output is correct
7 Correct 355 ms 8868 KB Output is correct
8 Correct 414 ms 13172 KB Output is correct
9 Correct 375 ms 7880 KB Output is correct
10 Runtime error 19 ms 4188 KB Execution killed with signal 11
11 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 504 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 69 ms 3924 KB Output is correct
5 Correct 298 ms 10872 KB Output is correct
6 Correct 355 ms 8868 KB Output is correct
7 Correct 414 ms 13172 KB Output is correct
8 Correct 375 ms 7880 KB Output is correct
9 Runtime error 19 ms 4188 KB Execution killed with signal 11
10 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 504 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 69 ms 3924 KB Output is correct
6 Correct 298 ms 10872 KB Output is correct
7 Correct 355 ms 8868 KB Output is correct
8 Correct 414 ms 13172 KB Output is correct
9 Correct 375 ms 7880 KB Output is correct
10 Runtime error 19 ms 4188 KB Execution killed with signal 11
11 Halted 0 ms 0 KB -