Submission #1233451

#	Time	Username	Problem	Language	Result	Execution time	Memory
1233451		inesfi	Swapping Cities (APIO20_swap)	C++20	0 / 100	2097 ms	18428 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];
bool deja[TAILLEMAXI];
int vraidist[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 bfs(){
    deque<int> ec={};
    ec.push_back(deb);
    int d=0;
    while (!ec.empty()){
        int taille=ec.size();
        for (int i=0;i<taille;i++){
            int a=ec.front();
            ec.pop_front();
            if (vraidist[a]==-1){
                vraidist[a]=d;
                for (auto j:adja[a]){
                    ec.push_back(autre(j,a));
                }
            }
        }
        d++;
    }
}

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;
    }
    for (int i=0;i<nbvilles;i++){
        surchemin[i]=false;
        deja[i]=false;
        vraidist[i]=-1;
    }
    bfs();
    dij();
    int distmin=dist[fin];
    int ec=fin;
    /*for (int i=0;i<nbvilles;i++){
        cout<<vraidist[i]<<" ";
    }
    cout<<endl;
    return 0;*/
    while (ec!=deb){
        deja[ec]=true;
        if (ec!=fin){
            surchemin[ec]=true;
        }
        int plusproche=INFINI,pos=-1,iroute=-1;
        //cout<<dist[autre(adja[ec][v],ec)]<<endl;
        for (auto i:adja[ec]){
            if (dist[autre(i,ec)]!=-1 and dist[autre(i,ec)]<=dist[ec] and deja[autre(i,ec)]==false){
                //cout<<42<<endl;
                if (vraidist[autre(i,ec)]<plusproche){
                    pos=autre(i,ec);
                    plusproche=vraidist[autre(i,ec)];
                    iroute=i;
                }
            }
        }
        possible[iroute]=false;
        ec=pos;
    }
    dij();
    int nouvdist=dist[fin];
    int rep=INFINI;
    if (nouvdist!=-1){
        rep=nouvdist;
    }
    int cote=INFINI;
    int undeb=INFINI,deuxdeb=INFINI,unfin=INFINI,deuxfin=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 (possible[i] and (get<0>(routes[i])==deb or get<1>(routes[i])==deb)){
            int l=get<2>(routes[i]);
            if (l<=undeb){
                deuxdeb=undeb;
                undeb=l;
            }
            else if (l<=deuxdeb){
                deuxdeb=l;
            }
        }
        if (possible[i] and (get<0>(routes[i])==fin or get<1>(routes[i])==fin)){
            int l=get<2>(routes[i]);
            if (l<=unfin){
                deuxfin=unfin;
                unfin=l;
            }
            else if (l<=deuxfin){
                deuxfin=l;
            }
        }
    }
    if (cote!=INFINI){
        rep=min(rep,max(distmin,cote));
    }
    if (undeb!=INFINI and deuxdeb!=INFINI){
        rep=min(rep,max(distmin,deuxdeb));
    }
    if (unfin!=INFINI and deuxfin!=INFINI){
        rep=min(rep,max(distmin,deuxfin));
    }
    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