oj.uz

Submission #811598

# Submission time Handle Problem Language Result Execution time Memory
811598 2023-08-07T05:04:07 Z tlnk07 Alias (COCI21_alias) C++17
70 / 70
 39 ms 472 KB 
#include<bits/stdc++.h>
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> mp;
 
int check(string x)
{
	if (mp.find(x) == mp.end())	mp[x] = cnt++;
	return mp[x];
}
 
int n, m, q;
vector<pii> e[maxn];
 
ll val[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[check(x)].push_back(pii(check(y), t));
	}
	cin >> q;
	while(q--)
	{
		string x, y;
		cin >> x >> y;
		set<pli> s;
		memset(val, -1, sizeof val);
		val[check(x)] = 0;
		s.insert(pli(0, check(x)));
		while (!s.empty())
		{
			pli curr = *s.begin();
			s.erase(curr);
			int curr_check = curr.second;
			for (int j = 0; j < (int)e[curr_check].size(); j++) {
				int nxt = e[curr_check][j].first;
				int d = e[curr_check][j].second;
				if (val[nxt] == -1 || val[nxt] > val[curr_check] + d) {
					s.erase(pli(val[nxt], nxt));
					val[nxt] = val[curr_check] + d;
					s.insert(pli(val[nxt], nxt));
				}
			}
		}
		if (val[check(y)] == -1)
			cout << "Roger" << endl;
		else	cout << val[check(y)] << endl;
	}
	return 0;
}

Subtask #1
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 352 KB Output is correct
3 Correct 24 ms 340 KB Output is correct
4 Correct 39 ms 472 KB Output is correct
5 Correct 4 ms 468 KB Output is correct
6 Correct 5 ms 468 KB Output is correct
7 Correct 4 ms 468 KB Output is correct