Submission #942393

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
942393	2024-03-10T15:00:39 Z	vjudge1	Alias (COCI21_alias)	C++17	70 / 70	7 ms	5724 KB

alias

#include "bits/stdc++.h"
using namespace std;
struct Nodo{
    long long Lugar, Tiempo;
};
vector< vector<Nodo> > Grafo;
long long n, m;
vector<long long> Dijkstra(long long Inicio){
    vector<long long> Distancia(n, 2222222222222222);
    Distancia[Inicio] = 0;
    set< pair<long long, long long> > Cola;
    Cola.insert(make_pair(0, Inicio));
    while(!Cola.empty()){
        pair<long long, long long> Actual = (*Cola.begin());
        Cola.erase((*Cola.begin()));
        for(auto E: Grafo[Actual.second]){
            if(Distancia[Actual.second] + E.Tiempo < Distancia[E.Lugar]){
                Distancia[E.Lugar] = Distancia[Actual.second] + E.Tiempo;
                Cola.insert(make_pair(E.Tiempo, E.Lugar));
            }
        }
    }
    return Distancia;
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin>>n>>m;
    set<string> s;
    vector<string> a(m);
    vector<string> b(m);
    vector<long long> c(m);
    for(long long i = 0; i < m; i++){
        cin>>a[i]>>b[i]>>c[i];
        s.insert(a[i]);
        s.insert(b[i]);
    }
    map<string, long long> Numerizar;
    long long i = 0;
    for(auto E: s){
        Numerizar[E] = i;
        i++;
    }
    Grafo.assign(n, vector<Nodo>());
    for(long long i = 0; i < m; i++){
        Nodo Arista;
        Arista.Lugar = Numerizar[b[i]];
        Arista.Tiempo = c[i];
        Grafo[Numerizar[a[i]]].push_back(Arista);
    }
    vector< vector<long long> > Distancias(n);
    vector<bool> Hechos(n, 0);
    long long q;
    cin>>q;
    while(q--){
        string Palabra, Objetivo;
        cin>>Palabra>>Objetivo;
        long long Revisar = Numerizar[Palabra];
        long long Buscar = Numerizar[Objetivo];
        if(Hechos[Revisar]){
            if(Distancias[Revisar][Buscar] == 2222222222222222) cout<<"Roger\n";
            else cout<<Distancias[Revisar][Buscar]<<"\n";
        } else {
            Distancias[Revisar] = Dijkstra(Revisar);
            Hechos[Revisar] = 1;
            if(Distancias[Revisar][Buscar] == 2222222222222222) cout<<"Roger\n";
            else cout<<Distancias[Revisar][Buscar]<<"\n";
        }
    }
    return 0;
}

Subtask #1

70.0 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	600 KB	Output is correct
2	Correct	1 ms	500 KB	Output is correct
3	Correct	3 ms	604 KB	Output is correct
4	Correct	7 ms	600 KB	Output is correct
5	Correct	5 ms	4956 KB	Output is correct
6	Correct	5 ms	4956 KB	Output is correct
7	Correct	5 ms	5724 KB	Output is correct