Submission #1233415

#	Time	Username	Problem	Language	Result	Execution time	Memory
1233415		inesfi	Swapping Cities (APIO20_swap)	C++20	0 / 100	2093 ms	17820 KiB

swap

#include "swap.h"
#include<bits/stdc++.h>
using namespace std;

const int TAILLEMAXI=200*1000+2,INFINI=1000*1000*1000+2;
int nbvilles,nbroutes;
int deb,fin;
vector<int> adja[TAILLEMAXI]; // num de la route
vector<tuple<int,int,int>> routes; // deb,fin,longueur
bool possible[TAILLEMAXI];
int dist[TAILLEMAXI];
bool surchemin[TAILLEMAXI];

int autre(int numroute,int moi){
    if (get<0>(routes[numroute])==moi){
        return get<1>(routes[numroute]);
    }
    return get<0>(routes[numroute]);
}

void dij(){
    for (int i=0;i<nbvilles;i++){
        dist[i]=-1;
    }
    set<pair<int,int>> encours;
    encours.clear();
    encours.insert({0,deb});
    while (!encours.empty()){
        int lmaxi=(*(encours.begin())).first;
        int endroit=(*(encours.begin())).second;
        encours.erase(encours.begin());
        if (dist[endroit]==-1){
            dist[endroit]=lmaxi;
            if (endroit==fin){
                return ;
            }
            for (auto i:adja[endroit]){
                if (possible[i]){
                    int a=autre(i,endroit);
                    if (dist[a]==-1){
                        encours.insert({max(lmaxi,get<2>(routes[i])),a});
                    }
                }
            }
        }
    }
}

void init(int N, int M,vector<int> U, vector<int> V, vector<int> W) {
    nbvilles=N;
    nbroutes=M;
    for (int i=0;i<nbroutes;i++){
        routes.push_back(make_tuple(U[i],V[i],W[i]));
        adja[U[i]].push_back(i);
        adja[V[i]].push_back(i);
    }
}

int getMinimumFuelCapacity(int X, int Y) {
    deb=X;
    fin=Y;
    for (int i=0;i<nbroutes;i++){
        possible[i]=true;
        surchemin[i]=false;
    }
    dij();
    int distmin=dist[fin];
    int ec=fin;
    while (ec!=deb){
        if (ec!=fin){
            surchemin[ec]=true;
        }
        int v=0;
        while (dist[autre(adja[ec][v],ec)]==-1 or dist[autre(adja[ec][v],ec)]>dist[ec]){
            v++;
        }
        possible[adja[ec][v]]=false;
        ec=autre(adja[ec][v],ec);
    }
    dij();
    int nouvdist=dist[fin];
    int rep=INFINI;
    if (nouvdist!=-1){
        rep=nouvdist;
    }
    int cote=INFINI;
    for (int i=0;i<nbroutes;i++){
        if (possible[i] and (surchemin[get<0>(routes[i])] or surchemin[get<1>(routes[i])])){
            cote=min(cote,get<2>(routes[i]));
        }
    }
    if (cote!=INFINI){
        rep=min(rep,max(distmin,cote));
    }
    if (rep==INFINI){
        return -1;
    }
    return rep;
}

• Subtask 1: 0 / 6
• Subtask 2: 0 / 7
• Subtask 3: 0 / 17
• Subtask 4: 0 / 20
• Subtask 5: 0 / 23
• Subtask 6: 0 / 27