Submission #397605

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
397605	2021-05-02T14:09:40 Z	MrRobot_28	Alias (COCI21_alias)	C++17	70 / 70	8 ms	8268 KB

alias

#include<bits/stdc++.h>
using namespace std;
#define X first
#define Y second
#define int long long
#define sz(a) (int)a.size()
const int mod = 998244353;

signed main()
{
  //  ifstream cin("input1.txt.4c");
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n, m;
    cin >> n >> m;
    map <string, int> mp;
    vector <pair <int, int> > g[n];
    int dist[n][n];
    int it = 0;
    for(int i = 0; i < m; i++)
    {
        string a, b;
        cin >> a >> b;
        int t;
        cin >> t;
        if(mp.count(a) == 0)
        {
            mp[a] = it++;
        }
        if(mp.count(b) == 0)
        {
            mp[b] = it++;
        }
        g[mp[a]].push_back({mp[b], t});
    }
    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < n; j++)
        {
            dist[i][j] = 1e18;
        }
        dist[i][i] = 0;
        priority_queue <pair <int, int> > q;
        q.push({0, i});
        while(sz(q) != 0)
        {
            int v = q.top().Y;
            int d = -q.top().X;
            q.pop();
            if(d != dist[i][v])
            {
                continue;
            }
            for(auto to : g[v])
            {
                if(dist[i][to.X] > d + to.Y)
                {
                    dist[i][to.X] = d + to.Y;
                    q.push({-dist[i][to.X], to.X});
                }
            }
        }
    }
    int q;
    cin >> q;
    while(q--)
    {
        string a, b;
        cin >> a >> b;
        if(dist[mp[a]][mp[b]] == 1e18)
        {
            cout << "Roger\n";
        }
        else{
            cout << dist[mp[a]][mp[b]] << "\n";
        }
    }
    return 0;
}

Subtask #1

70.0 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	3 ms	344 KB	Output is correct
4	Correct	5 ms	332 KB	Output is correct
5	Correct	7 ms	6604 KB	Output is correct
6	Correct	7 ms	6636 KB	Output is correct
7	Correct	8 ms	8268 KB	Output is correct