Submission #483875

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
483875	2021-11-01T07:02:33 Z	Sohsoh84	Alias (COCI21_alias)	C++17	70 / 70	19 ms	480 KB

alias

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;

#define all(x)                      (x).begin(),(x).end()
#define X                           first
#define Y                           second
#define sep                         ' '
#define endl                        '\n'
#define debug(x)                    cerr << #x << ": " <<  x << endl;

const ll MAXN = 1e3 + 10;
const ll INF = 1e16;
const ll MOD = 1e9 + 7; // 998244353;

ll dist[MAXN];
int n, m, ind = 0;
vector<pll> adj[MAXN];
map<string, int> mp;

inline int Vert(string s) {
	auto it = mp.find(s);
	if (it == mp.end()) {
		mp[s] = ind;
		ind++;
		return ind - 1;
	}

	return it -> Y;
}

inline void Dijkstra(int s) {
	memset(dist, 63, sizeof dist);
	priority_queue<pll, vector<pll>, greater<pll>> pq;
	dist[s] = 0;
	pq.push({0, s});

	while (!pq.empty()) {
		ll d_v = pq.top().X, v = pq.top().Y;
		pq.pop();
		if (d_v != dist[v]) continue;

		for (pll e : adj[v]) {
			ll u = e.X, d_u = d_v + e.Y;
			if (d_u < dist[u]) {
				dist[u] = d_u;
				pq.push({d_u, u});
			}
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int w;
		string s, t;
		cin >> s >> t >> w;
		adj[Vert(s)].push_back({Vert(t), w});
	}

	int q;
	cin >> q;
	while (q--) {
		string s, t;
		cin >> s >> t;
		int v = Vert(s), u = Vert(t);
		Dijkstra(v);
		if (dist[u] > INF) cout << "Roger" << endl;
		else cout << dist[u] << endl;
	}
	return 0;
}

Subtask #1

70.0 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	332 KB	Output is correct
2	Correct	0 ms	332 KB	Output is correct
3	Correct	12 ms	464 KB	Output is correct
4	Correct	19 ms	480 KB	Output is correct
5	Correct	3 ms	460 KB	Output is correct
6	Correct	3 ms	460 KB	Output is correct
7	Correct	3 ms	480 KB	Output is correct