Submission #671927

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
671927	2022-12-14T09:32:53 Z	Kenpar	Alias (COCI21_alias)	C++17	70 / 70	93 ms	620 KB

alias

#include "bits/stdc++.h"
using namespace std;
 
#define ll long long
#define endl '\n'
 
const ll MOD = 1e9+7;
const ll INF = 1e18;
const ll MAX = 2500;

void solve(){
	map<string,int> toInt;
	set<string> used;
	int n,m;
	cin>>n>>m;

	int cur = 0;
	vector<vector<pair<ll,ll>>> edges(n);
	for(int i = 0; i < m; i++){
		string a,b; ll c;
		cin>>a>>b>>c;

		int aInd, bInd;
		if(!used.count(a)){
			aInd = cur;
			toInt[a] = cur;
			cur++;
			used.insert(a);
		}else{
			aInd = toInt[a];
		}

		if(!used.count(b)){
			bInd = cur;
			toInt[b] = cur;
			cur++;
			used.insert(b);
		}else{
			bInd = toInt[b];
		}

		edges[aInd].push_back({bInd, c});
	}

	int q;
	cin>>q;

	for(int i = 0; i < q; i++){
		vector<ll> dist(n, INF);

		string aTemp, bTemp; cin>>aTemp>>bTemp;
		int a = toInt[aTemp], b = toInt[bTemp];

		priority_queue<pair<ll,ll>, vector<pair<ll,ll>>, greater<pair<ll,ll>>> pq;

		pq.push({0,a});

		while(!pq.empty()){
			pair<ll,ll> top = pq.top();
			pq.pop();

			if(dist[top.second] <= top.first) continue;

			dist[top.second] = top.first;

			for(pair<ll,ll> edge : edges[top.second]){
				pq.push({top.first + edge.second, edge.first});
			}
		}

		if(dist[b] == INF) cout<<"Roger";
		else cout<<dist[b];

		cout<<endl;
	}
}

int main() 
{
    cin.tie(NULL);
    ios::sync_with_stdio(NULL);
    int t = 1;
    //cin>>t;

    int temp = t;
    while(t--){
        //cout<<"Case #"<<temp - t<<" > "<<endl;
        solve();
 
        cout<<endl;
    }

}

Compilation message

alias.cpp: In function 'int main()':
alias.cpp:85:9: warning: unused variable 'temp' [-Wunused-variable]
   85 |     int temp = t;
      |         ^~~~

Subtask #1

70.0 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	93 ms	456 KB	Output is correct
4	Correct	83 ms	476 KB	Output is correct
5	Correct	3 ms	620 KB	Output is correct
6	Correct	3 ms	596 KB	Output is correct
7	Correct	3 ms	596 KB	Output is correct