oj.uz

Submission #985245

# Submission time Handle Problem Language Result Execution time Memory
985245 2024-05-17T13:45:33 Z Aiperiii Swapping Cities (APIO20_swap) C++14
0 / 100
 2000 ms 28268 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 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) {
    vector <vector <int> > d(n,vector <int> (n,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 756 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 66 ms 2464 KB Output is correct
5 Correct 333 ms 10472 KB Output is correct
6 Correct 356 ms 8484 KB Output is correct
7 Correct 444 ms 13208 KB Output is correct
8 Correct 417 ms 8036 KB Output is correct
9 Runtime error 25 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 756 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Runtime error 51 ms 7924 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 756 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 66 ms 2464 KB Output is correct
5 Correct 333 ms 10472 KB Output is correct
6 Correct 356 ms 8484 KB Output is correct
7 Correct 444 ms 13208 KB Output is correct
8 Correct 417 ms 8036 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 883 ms 22096 KB Output is correct
11 Correct 925 ms 14000 KB Output is correct
12 Correct 952 ms 17692 KB Output is correct
13 Correct 693 ms 16480 KB Output is correct
14 Correct 720 ms 7532 KB Output is correct
15 Correct 881 ms 8284 KB Output is correct
16 Correct 880 ms 9292 KB Output is correct
17 Correct 873 ms 10728 KB Output is correct
18 Correct 1087 ms 25496 KB Output is correct
19 Correct 686 ms 14416 KB Output is correct
20 Correct 906 ms 14288 KB Output is correct
21 Correct 1836 ms 22924 KB Output is correct
22 Correct 250 ms 3412 KB Output is correct
23 Correct 769 ms 12204 KB Output is correct
24 Execution timed out 2054 ms 28268 KB Time limit exceeded
25 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 756 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 66 ms 2464 KB Output is correct
6 Correct 333 ms 10472 KB Output is correct
7 Correct 356 ms 8484 KB Output is correct
8 Correct 444 ms 13208 KB Output is correct
9 Correct 417 ms 8036 KB Output is correct
10 Runtime error 25 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 756 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 66 ms 2464 KB Output is correct
5 Correct 333 ms 10472 KB Output is correct
6 Correct 356 ms 8484 KB Output is correct
7 Correct 444 ms 13208 KB Output is correct
8 Correct 417 ms 8036 KB Output is correct
9 Runtime error 25 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 348 KB Output is correct
2 Correct 1 ms 756 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 66 ms 2464 KB Output is correct
6 Correct 333 ms 10472 KB Output is correct
7 Correct 356 ms 8484 KB Output is correct
8 Correct 444 ms 13208 KB Output is correct
9 Correct 417 ms 8036 KB Output is correct
10 Runtime error 25 ms 4188 KB Execution killed with signal 11
11 Halted 0 ms 0 KB -