Submission #985231

#	Time	Username	Problem	Language	Result	Execution time	Memory
985231		Aiperiii	Swapping Cities (APIO20_swap)	C++14	0 / 100	2031 ms	36416 KiB

swap

#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
• Subtask 2: 0 / 7
• Subtask 3: 0 / 17
• Subtask 4: 0 / 20
• Subtask 5: 0 / 23
• Subtask 6: 0 / 27