Submission #626539

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
626539	2022-08-11T14:13:02 Z	Toqa44	Alias (COCI21_alias)	C++17	70 / 70	40 ms	472 KB

alias

#include <bits/stdc++.h>

#define  endl "\n"

using namespace std;

typedef long long ll;
ll n, m, ans, a, q , dis[1009] , pa[1009] , o;
string x, y ;
map<string ,ll>mp ;
vector<pair<ll,ll>>v[1009];
set <pair<ll,ll>> ss;
bool vis [1009];

int main()
{
    ios::sync_with_stdio;cin.tie();cout.tie();

        cin >> n >> m;
        ll j = 1 ;
        for(int i = 0; i < m ; i++)
            {
                cin >> x >> y >> a ;
                if(mp[x] == 0)
                {
                    mp[x] = j ;
                    j++ ;
                }

                if(mp[y] == 0)
                {
                    mp[y] = j ;
                    j++ ;
                }



                v[mp[x]].push_back({mp[y],a});
            }



            cin >> q ;
            while(q--)
            {
                ss.clear() ;
                for( int i = 1 ; i <= n ; i++)
                {
                     dis[i] = 1e18 ;
                     vis[i] = 0 ;
                }

                cin >> x >> y ;
                ss.insert({0,mp[x]});
                dis[mp[x]] = 0 ;
                while(!ss.empty())
                {
                    pair<ll,ll>u = *ss.begin();
                    ss.erase(u) ;
                    ll node = u.second ;
                    if(vis[node]) continue ;
                    vis[node] = 1 ;
                    for(auto p : v[node])
                    {
                        ll k = p.first ;
                        ll h = p.second ;
                        if(dis[k] > dis[node] + h)
                        {
                            pa[k] = node ;
                            dis[k] = dis[node] + h ;
                            ss.insert({dis[k],k}) ;
                        }
                    }

                }
                if(dis[mp[y]] == 1e18 )
                    cout << "Roger" << endl ;
                else
                cout << dis[mp[y]] << endl ;



            }

    return 0;
}

/*
3 2
novak goat 1
goat simulator 3
2
novak simulator
simulator goat
*/

Compilation message

alias.cpp: In function 'int main()':
alias.cpp:17:10: warning: statement is a reference, not call, to function 'std::ios_base::sync_with_stdio' [-Waddress]
   17 |     ios::sync_with_stdio;cin.tie();cout.tie();
      |     ~~~~~^~~~~~~~~~~~~~~
alias.cpp:17:10: warning: statement has no effect [-Wunused-value]

Subtask #1

70.0 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	328 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	26 ms	340 KB	Output is correct
4	Correct	40 ms	468 KB	Output is correct
5	Correct	6 ms	468 KB	Output is correct
6	Correct	6 ms	468 KB	Output is correct
7	Correct	9 ms	472 KB	Output is correct