oj.uz

Submission #517665

# Submission time Handle Problem Language Result Execution time Memory
517665 2022-01-23T06:45:58 Z ivls Alias (COCI21_alias) C++14
0 / 70
 150 ms 7628 KB 
#include <bits/stdc++.h>

using namespace std;

int n, m;
map<string, int> nn;
vector<int> g[5000];
int dst[5000][5000];

int dist(int st, int fi) {
    int dist[5000] = {};
    set<pair<int, int>> s;
    for (int i = 1; i <= n; i++) {
        s.insert(make_pair((i == st ? 0 : 2000000000), i));
        dist[i] = (i == st ? 0 : 2000000000);
    }
    while (!s.empty()) {
        int r = (*s.begin()).first, v = (*s.begin()).second;
        s.erase(s.begin());
        for (int u : g[v]) {
            if (dist[u] > dist[v] + dst[v][u]) {
                s.erase(make_pair(u, dist[u]));
                s.insert(make_pair(u, dist[v] + dst[v][u]));
                dist[u] = dist[v] + dst[v][u];
            }
        }
    }
    return dist[fi] == 2000000000 ? -1 : dist[fi];
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n >> m;
    int ii = 0;
    for (int i = 0; i < m; i++) {
        string u, v;
        cin >> u >> v;
        int t;
        cin >> t;
        if (nn[u] == 0) {
            nn[u] = ++ii;
        }
        if (nn[v] == 0) {
            nn[v] = ++ii;
        }
        g[nn[u]].push_back(nn[v]);
        dst[nn[u]][nn[v]] = t;
    }
    int qq;
    cin >> qq;
    while (qq--) {
        string a, b;
        cin >> a >> b;
        if (nn[a] == 0) {
            nn[a] = ++ii;
        }
        if (nn[b] == 0) {
            nn[b] = ++ii;
        }
        int r = dist(nn[a], nn[b]);
        if (r == -1) {
            cout << "Roger" << '\n';
        }
        else {
            cout << r << '\n';
        }
    }

    return 0;
}

Compilation message

alias.cpp: In function 'int dist(int, int)':
alias.cpp:18:13: warning: unused variable 'r' [-Wunused-variable]
   18 |         int r = (*s.begin()).first, v = (*s.begin()).second;
      |             ^

Subtask #1
0 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 600 KB Output isn't correct
2 Runtime error 4 ms 744 KB Execution killed with signal 11
3 Incorrect 47 ms 748 KB Output isn't correct
4 Runtime error 5 ms 1740 KB Execution killed with signal 11
5 Incorrect 139 ms 3676 KB Output isn't correct
6 Incorrect 150 ms 3632 KB Output isn't correct
7 Runtime error 18 ms 7628 KB Execution killed with signal 11