Submission #471659

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
471659	2021-09-10T08:23:09 Z	LeeRise	Alias (COCI21_alias)	C++14	70 / 70	26 ms	464 KB

alias

#include<bits/stdc++.h>
#define faster ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define fi first
#define se second
using namespace std;
const int maxn=1005;
const int oo=1e18;
int tam=0;
map<string,int> id;
vector<pair<int,int>> e[maxn];
long long memo[maxn];

int getid(string x)
{
	if(id.find(x)==id.end())
		id[x]=++tam;
	return id[x];
}
void dijkstra(int x)
{
	priority_queue<pair<long long,int>> pq;
	memo[x]=0;
	pq.emplace(0,x);
	while(!pq.empty())
	{
		auto [dd,y]=pq.top();
		pq.pop();
		if(memo[y]!=-dd)
			continue;
		for(auto [v,c]:e[y])
		{
			if(memo[v]>memo[y]+c)
			{
				memo[v]=memo[y]+c;
				pq.emplace(-memo[v],v);
			}
		}
	}
	return;
}
int main()
{
	faster
	//freopen("ALIAS.INP", "r", stdin);
	//freopen("ALIAS.OUT", "w", stdout);
	int n,m,q;
	cin >> n >> m;
	for(int i=1;i<=m;i++)
	{
		string a,b;
		int c;
		cin >> a >> b >> c;
		e[getid(a)].emplace_back(getid(b),c);
	}
	cin>>q;
	while(q--)
	{
		string a,b;
		cin >> a >> b;
		for(int i=1;i<=n;i++)
			memo[i]=oo;
        int x, y;
        x=getid(a);
        y=getid(b);
		dijkstra(x);
		if(memo[y]==oo)
			cout<<"Roger" << endl;
		else
			cout<< memo[y]<< endl;
	}
	return 0;
}

Compilation message

alias.cpp:7:14: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
    7 | const int oo=1e18;
      |              ^~~~
alias.cpp: In function 'void dijkstra(int)':
alias.cpp:26:8: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   26 |   auto [dd,y]=pq.top();
      |        ^
alias.cpp:30:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   30 |   for(auto [v,c]:e[y])
      |            ^

Subtask #1

70.0 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	332 KB	Output is correct
2	Correct	1 ms	332 KB	Output is correct
3	Correct	18 ms	332 KB	Output is correct
4	Correct	26 ms	464 KB	Output is correct
5	Correct	6 ms	460 KB	Output is correct
6	Correct	6 ms	460 KB	Output is correct
7	Correct	6 ms	460 KB	Output is correct