Submission #492765

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
492765	2021-12-08T20:38:18 Z	inksamurai	Alias (COCI21_alias)	C++17	50 / 70	21 ms	664 KB

alias

#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define sz(a) (ll)a.size()
#define all(a) a.begin(),a.end()
#define rep(i,n) for(ll i=0;i<n;i++)
#define crep(i,x,n) for(ll i=x;i<n;i++)
#define drep(i,n) for(ll i=n-1;i>=0;i--)
#define vec(...) vector<__VA_ARGS__>
#define _3cSpNGp ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
typedef long long ll;
typedef long double ld;
using pii=pair<ll,ll>;
using vi=vector<ll>;

int main(){
_3cSpNGp;
	ll n,m;
	cin>>n>>m;
	vec(string) tmp;
	vec(tuple<string,string,ll>) inp;
	rep(i,m){
		string a,b;
		ll t;
		cin>>a>>b>>t;
		inp.pb({a,b,t});
		tmp.pb(a);
		tmp.pb(b);
	}
	// ~
	sort(all(tmp));
	tmp.erase(unique(all(tmp)),tmp.end());
	std::map<string,ll> mp;
	rep(i,sz(tmp)) mp[tmp[i]]=i;
	const ll k=sz(tmp);
	// ~
	vec(vec(pii)) adj(k);	
	rep(i,sz(inp)){
		auto [a,b,t]=inp[i];
		adj[mp[a]].pb({mp[b],t});
	}
	auto dkst=[&](ll hm,ll need)->ll{
		vi dp(k,1e9);
		dp[hm]=0;
		priority_queue<pii,vec(pii),greater<pii>> pq;
		pq.push({0,hm});
		while(sz(pq)){
			pii p=pq.top();
			ll v=p.se,cost=p.fi;
			pq.pop();
			if(dp[v]!=cost) continue;
			for(auto edge : adj[v]){
				ll u=edge.fi,now=edge.se;
				if(dp[u]>now+cost){
					dp[u]=now+cost;
					pq.push({now+cost,u});
				}
			}
		}
		return dp[need];
	};
	ll q;
	cin>>q;
	rep(_,q){
		string a,b;
		cin>>a>>b;
		if(mp.find(a)==mp.end() or mp.find(b)==mp.end()){
			cout<<"Roger\n";
		}else{
			ll val=dkst(mp[a],mp[b]);
			if(val==1e9) cout<<"Roger\n";
			else cout<<val<<"\n";
		}
	}
//	
	return 0;
}

Subtask #1

50.0 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	1 ms	332 KB	Output is correct
3	Correct	17 ms	588 KB	Output is correct
4	Incorrect	21 ms	564 KB	Output isn't correct
5	Correct	4 ms	588 KB	Output is correct
6	Correct	4 ms	664 KB	Output is correct
7	Incorrect	4 ms	588 KB	Output isn't correct