Submission #469386

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
469386	2021-08-31T17:48:15 Z	ala2	Alias (COCI21_alias)	C++14	70 / 70	59 ms	95072 KB

alias

#include <bits/stdc++.h>

using namespace std;
vector<pair<int,int>>graph[1001000];
string s[1001000];
string c[1010000];
const int inf=1e17;
int w[1001000];
map<string ,int>mm;
vector<string>v;
map<string ,int>vi;
int dst[1010][1010];
int vstd[1010][1010];
int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=0;i<m;i++)
    {

        cin>>s[i]>>c[i];
        cin>>w[i];
        if(!vi[s[i]])
        {
            vi[s[i]]=1;
            v.push_back(s[i]);
        }
        if(!vi[c[i]])
        {
            vi[c[i]]=1;
            v.push_back(c[i]);
        }
    }
    for(int i=0;i<v.size();i++)
    {
        mm[v[i]]=i+1;
    }
    for(int i=0;i<m;i++)
    {
        graph[mm[s[i]]].push_back({mm[c[i]],w[i]});
    }




   for(int g=1;g<=n;g++){
    priority_queue<pair<int,int>>pq;
    pq.push({-0,g});
    for(int i=1;i<=n;i++)
        dst[g][i]=inf;
    dst[g][g]=0;
    while(!pq.empty())
    {// cout<<endl;
        int dist = -pq.top().first;//because we pushed it with minus distance
        int node = pq.top().second;
        pq.pop();
        if(vstd[g][node])
            continue;
        vstd[g][node] = 1;
        for(auto u:graph[node])
        {
            int new_distance = dist + u.second;//distance of new node = distance of this node + weight
            if(new_distance<dst[g][u.first])
            {
                pq.push({-new_distance,u.first});
                dst[g][u.first] = new_distance;
            }
        }
    }
   }
   int u;
   cin>>u;
   while(u--)
   {
       string s,c;
       cin>>s>>c;
       if(dst[mm[s]][mm[c]]!=inf)
       {
           cout<<dst[mm[s]][mm[c]]<<endl;
       }
       else cout<<"Roger"<<endl;
   }
}

Compilation message

alias.cpp:7:15: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+17' to '2147483647' [-Woverflow]
    7 | const int inf=1e17;
      |               ^~~~
alias.cpp: In function 'int main()':
alias.cpp:34:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::__cxx11::basic_string<char> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |     for(int i=0;i<v.size();i++)
      |                 ~^~~~~~~~~

Subtask #1

70.0 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	45 ms	86712 KB	Output is correct
2	Correct	46 ms	86836 KB	Output is correct
3	Correct	52 ms	87236 KB	Output is correct
4	Correct	58 ms	87756 KB	Output is correct
5	Correct	59 ms	94092 KB	Output is correct
6	Correct	55 ms	94148 KB	Output is correct
7	Correct	56 ms	95072 KB	Output is correct