Submission #1046528

#	Time	Username	Problem	Language	Result	Execution time	Memory
1046528		inesfi	Crocodile's Underground City (IOI11_crocodile)	C++14	100 / 100	409 ms	48468 KiB

crocodile

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

//#define int long long

const int TAILLEMAXI=100*1000+2,INFINI=1000*1000*1000+2;
int noeud[TAILLEMAXI];
int fin[TAILLEMAXI];
int proches[TAILLEMAXI][2]; // numnoeud, premier ou deuxieme dist
vector<pair<int,int>> adja[TAILLEMAXI]; // noeud, dist
int d1,d2,ec,dist,num,chem;
set<pair<int,int>> encours;

int travel_plan(int nbnoeuds, int nbchemins, int chemins[][2], int L[], int nbsorties, int sorties[]){
    for (int i=0;i<nbchemins;i++){
        adja[chemins[i][0]].push_back({chemins[i][1],L[i]});
        adja[chemins[i][1]].push_back({chemins[i][0],L[i]});
    }
    for (int i=0;i<nbsorties;i++){
        fin[sorties[i]]=1;
    }
    for (int ipers=0;ipers<nbnoeuds;ipers++){
        if (fin[ipers]==0){
            d1=INFINI;
            d2=INFINI;
            for (int i=0;i<(int)adja[ipers].size();i++){
                if (fin[adja[ipers][i].first]==1){
                    if (adja[ipers][i].second<d1){
                        d2=d1;
                        d1=adja[ipers][i].second;
                    }
                    else if (adja[ipers][i].second<d2){
                        d2=adja[ipers][i].second;
                    }
                }
            }
            proches[ipers][0]=d1;
            proches[ipers][1]=d2;
            encours.insert({d2,ipers});
        }
    }
    while (encours.size()!=0){
        ec=(*(encours.begin())).second;
        dist=(*(encours.begin())).first;
        noeud[ec]=dist;
        encours.erase(encours.begin());
        fin[ec]=1;
        for (int i=0;i<(int)adja[ec].size();i++){
            if (fin[adja[ec][i].first]==0){
                num=adja[ec][i].first;
                chem=adja[ec][i].second;
                if (proches[num][0]>chem+dist){
                    encours.erase({proches[num][1],num});
                    encours.insert({proches[num][0],num});
                    proches[num][1]=proches[num][0];
                    proches[num][0]=chem+dist;
                }
                else if (proches[num][1]>chem+dist){
                    encours.erase({proches[num][1],num});
                    encours.insert({chem+dist,num});
                    proches[num][1]=chem+dist;
                }
            }
        }
    }
    return proches[0][1];
}

• Subtask 1: 46 / 46
• Subtask 2: 43 / 43
• Subtask 3: 11 / 11