Submission #812299

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
812299	2023-08-07T08:16:06 Z	Tunglam07	Alias (COCI21_alias)	C++17	70 / 70	38 ms	468 KB

alias

#include<bits/stdc++.h>
using namespace std;
 
map<string, int> mp;
vector<pair<int, int> > vec[1001];
long long dp[1001], cnt, n, m, q;
 
int ckstr(string x)
{
	if (mp.find(x) == mp.end())	
	{
		mp[x] = cnt++;
	}
	return mp[x];
}

int main() 
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m;
	for (int i = 0; i < m; i++) 
	{
		int t;
		string x, y;
		cin >> x >> y >> t;
		vec[ckstr(x)].push_back(pair<int, int>(ckstr(y), t));
	}
	cin >> q;
	while(q--)
	{
		string x, y;
		cin >> x >> y;
		set<pair<long long, int> > s;
		memset(dp, -1, sizeof dp);
		dp[ckstr(x)] = 0;
		s.insert(pair<long long, int>(0, ckstr(x)));
		while (!s.empty())
		{
			pair<long long, int> id = *s.begin();
			s.erase(id);
			int ckid = id.second;
			for (int j = 0; j < (int)vec[ckid].size(); j++) 
			{
				int nxt = vec[ckid][j].first;
				int d = vec[ckid][j].second;
				if (dp[nxt] == -1 || dp[nxt] > dp[ckid] + d) 
				{
					s.erase(pair<long long, int>(dp[nxt], nxt));
					dp[nxt] = dp[ckid] + d;
					s.insert(pair<long long, int>(dp[nxt], nxt));
				}
			}
		}
		if (dp[ckstr(y)] == -1)
		{
			cout << "Roger" << endl;
		}
		else	
		{
			cout << dp[ckstr(y)] << endl;
		}
	}
}

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	348 KB	Output is correct
3	Correct	24 ms	340 KB	Output is correct
4	Correct	38 ms	468 KB	Output is correct
5	Correct	4 ms	468 KB	Output is correct
6	Correct	4 ms	468 KB	Output is correct
7	Correct	4 ms	468 KB	Output is correct