oj.uz

Submission #619313

# Submission time Handle Problem Language Result Execution time Memory
619313 2022-08-02T11:05:31 Z Hussein3602 Alias (COCI21_alias) C++14
70 / 70
 186 ms 3668 KB 
#include<bits/stdc++.h>

using namespace std ;

typedef long long ll ;

const int N=1e5;

int n , m , cnt=1 , q ;

vector< pair<ll,ll> > edges[N] ;

vector<ll>dist(N,-1) ;

map<string,ll>mp ;

ll bfs(int src, int traget)
{
    set < pair<ll,ll> > s ;
    s.insert({0,src}) ;
    while(!s.empty())
    {
        pair<ll,ll> p = *s.begin() ;
        s.erase(p) ;
        ll node=p.second , nodecost=p.first ;
        if(dist[node]!=-1)continue ;
        dist[node]=nodecost;
        for( pair<ll,ll> edge :edges[node])
        {
            s.insert({nodecost+edge.second,edge.first}) ;
        }
    }
    if(dist[traget]!=-1)return dist[traget];
    return -1;
}
int main()
{
    cin >> n >> m ;
    for(int i=0;i<m;i++)
    {
        string x , y ;

        ll t ;

        cin >> x >> y >> t ;

        if(mp[x]==0)mp[x]=cnt++;

        if(mp[y]==0)mp[y]=cnt++;

        edges[mp[x]].push_back({mp[y],t}) ;
    }
    cin >> q ;
    while(q--)
    {
        string x , y ;
        cin >> x >> y ;
        ll d=bfs(mp[x],mp[y]) ;
        if(d==-1)cout<<"Roger"<<endl;
        else cout<<d<<endl;
        for(int i=0;i<=1000;i++)dist[i]=-1;
    }
}

Subtask #1
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3412 KB Output is correct
2 Correct 2 ms 3412 KB Output is correct
3 Correct 164 ms 3588 KB Output is correct
4 Correct 186 ms 3540 KB Output is correct
5 Correct 7 ms 3540 KB Output is correct
6 Correct 8 ms 3588 KB Output is correct
7 Correct 8 ms 3668 KB Output is correct