Submission #445450

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
445450	2021-07-18T04:21:43 Z	retsiger	Alias (COCI21_alias)	C++14	70 / 70	22 ms	8440 KB

alias

#include<bits/stdc++.h>
#define x first
#define y second
#define bug(x) cerr<<#x<<" = "<<x<<'\n'

using namespace std;
using ll = long long;

const int maxn = 1005;
const ll INF = 1e18;

typedef pair <int, int> ii;

int N, M, cn;
map <string, int> num;
vector <ii> G[maxn];
ll D[maxn][maxn];

int main() {
  ios::sync_with_stdio(0); cin.tie(0);
  cin >> N >> M;
  for (int i = 0; i < M; ++i) {
    string u, v; int t;
    cin >> u >> v >> t;
    int x, y;
    if (num[u]) x = num[u];
    else x = num[u] = ++cn;
    if (num[v]) y = num[v];
    else y = num[v] = ++cn;
    G[x].push_back({y, t});
    bug(x);
    bug(y);
  }
  memset(D, 0x7f, sizeof D);
  for (int u = 1; u <= N; ++u) {
    D[u][u] = 0;
    priority_queue <ii, vector<ii>, greater<ii>> q;
    q.push({0, u});
    while (q.size()) {
      ii cur = q.top(); q.pop();
      if (cur.x > D[u][cur.y]) continue;
      int x = cur.y;
      for (auto p : G[x]) {
        int y = p.x, t = p.y;
        if (D[u][y] > D[u][x] + t) {
          D[u][y] = D[u][x] + t;
          q.push({D[u][y], y});
        }
      }
    }
  }
  int q; cin >> q;
  while (q--) {
    string u, v; cin >> u >> v;
    int x = num[u], y = num[v];
    if (D[x][y] > INF) {
      cout << "Roger\n";
    } else
      cout << D[x][y] << '\n';
  }
  return 0;
}

Subtask #1

70.0 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	8140 KB	Output is correct
2	Correct	5 ms	8140 KB	Output is correct
3	Correct	18 ms	8268 KB	Output is correct
4	Correct	22 ms	8404 KB	Output is correct
5	Correct	19 ms	8404 KB	Output is correct
6	Correct	19 ms	8440 KB	Output is correct
7	Correct	19 ms	8416 KB	Output is correct