oj.uz

Submission #985231

# Submission time Handle Problem Language Result Execution time Memory
985231 2024-05-17T13:26:06 Z Aiperiii Swapping Cities (APIO20_swap) C++14
0 / 100
 2000 ms 36416 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 <vector <int> > st;
    st.insert({0,X,Y});
    while(!st.empty()){
        vector <int> v=*st.begin();
        st.erase(st.begin());
        int a=v[1],b=v[2];
        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 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 106 ms 4692 KB Output is correct
5 Correct 474 ms 14028 KB Output is correct
6 Correct 512 ms 11092 KB Output is correct
7 Correct 705 ms 17940 KB Output is correct
8 Correct 662 ms 9768 KB Output is correct
9 Runtime error 19 ms 5980 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 344 KB Output is correct
3 Runtime error 49 ms 11932 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 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 106 ms 4692 KB Output is correct
5 Correct 474 ms 14028 KB Output is correct
6 Correct 512 ms 11092 KB Output is correct
7 Correct 705 ms 17940 KB Output is correct
8 Correct 662 ms 9768 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1421 ms 31028 KB Output is correct
11 Correct 1418 ms 18884 KB Output is correct
12 Correct 1523 ms 24472 KB Output is correct
13 Correct 1029 ms 23804 KB Output is correct
14 Correct 1179 ms 10096 KB Output is correct
15 Correct 1481 ms 10324 KB Output is correct
16 Correct 1403 ms 11972 KB Output is correct
17 Correct 1445 ms 14168 KB Output is correct
18 Correct 1728 ms 36416 KB Output is correct
19 Correct 1194 ms 21584 KB Output is correct
20 Correct 1497 ms 19408 KB Output is correct
21 Execution timed out 2031 ms 32724 KB Time limit exceeded
22 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 106 ms 4692 KB Output is correct
6 Correct 474 ms 14028 KB Output is correct
7 Correct 512 ms 11092 KB Output is correct
8 Correct 705 ms 17940 KB Output is correct
9 Correct 662 ms 9768 KB Output is correct
10 Runtime error 19 ms 5980 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 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 106 ms 4692 KB Output is correct
5 Correct 474 ms 14028 KB Output is correct
6 Correct 512 ms 11092 KB Output is correct
7 Correct 705 ms 17940 KB Output is correct
8 Correct 662 ms 9768 KB Output is correct
9 Runtime error 19 ms 5980 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 1 ms 348 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 106 ms 4692 KB Output is correct
6 Correct 474 ms 14028 KB Output is correct
7 Correct 512 ms 11092 KB Output is correct
8 Correct 705 ms 17940 KB Output is correct
9 Correct 662 ms 9768 KB Output is correct
10 Runtime error 19 ms 5980 KB Execution killed with signal 11
11 Halted 0 ms 0 KB -