oj.uz

Submission #386343

# Submission time Handle Problem Language Result Execution time Memory
386343 2021-04-06T12:21:31 Z model_code Alias (COCI21_alias) C++17
70 / 70
 52 ms 512 KB 
#include <map>
#include <set>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

typedef long long ll;
typedef pair<ll, int> pli;
typedef pair<int, int> pii;

const int maxn = 1005;

int cnt;
map<string, int> ind_map;

int ind(string x) {
    if (ind_map.find(x) == ind_map.end())
        ind_map[x] = cnt++;
    return ind_map[x];
}

int n, m, q;
vector<pii> e[maxn];

ll dist[maxn];

int main() {
    ios::sync_with_stdio(false);
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int t;
        string x, y;
        cin >> x >> y >> t;
        e[ind(x)].push_back(pii(ind(y), t));
    }
    cin >> q;
    for (int i = 0; i < q; i++) {
        string x, y;
        cin >> x >> y;
        set<pli> s;
        memset(dist, -1, sizeof dist);
        dist[ind(x)] = 0;
        s.insert(pli(0, ind(x)));
        while (!s.empty()) {
            pli curr = *s.begin();
            s.erase(curr);
            int curr_ind = curr.second;
            for (int j = 0; j < (int)e[curr_ind].size(); j++) {
                int nxt = e[curr_ind][j].first;
                int d = e[curr_ind][j].second;
                if (dist[nxt] == -1 || dist[nxt] > dist[curr_ind] + d) {
                    s.erase(pli(dist[nxt], nxt));
                    dist[nxt] = dist[curr_ind] + d;
                    s.insert(pli(dist[nxt], nxt));
                }
            }
        }
        if (dist[ind(y)] == -1)
            cout << "Roger" << endl;
        else
            cout << dist[ind(y)] << endl;
    }
    return 0;
}

Subtask #1
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 34 ms 364 KB Output is correct
4 Correct 52 ms 364 KB Output is correct
5 Correct 8 ms 492 KB Output is correct
6 Correct 8 ms 492 KB Output is correct
7 Correct 8 ms 512 KB Output is correct