oj.uz

Submission #397604

# Submission time Handle Problem Language Result Execution time Memory
397604 2021-05-02T14:08:42 Z MrRobot_28 Alias (COCI21_alias) C++17
50 / 70
 9 ms 8376 KB 
#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] = 1e9;
        }
        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]] == 1e9)
        {
            cout << "Roger\n";
        }
        else{
            cout << dist[mp[a]][mp[b]] << "\n";
        }
    }
    return 0;
}

Subtask #1
50.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 316 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 3 ms 332 KB Output is correct
4 Incorrect 5 ms 460 KB Output isn't correct
5 Correct 8 ms 6592 KB Output is correct
6 Correct 9 ms 6632 KB Output is correct
7 Incorrect 9 ms 8376 KB Output isn't correct