Submission #415375

#	Time	Username	Problem	Language	Result	Execution time	Memory
415375		sam571128	Alias (COCI21_alias)	C++17	70 / 70	12 ms	8524 KiB

alias

#include <bits/stdc++.h>
#include <bits/extc++.h>

#define int long long
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

using namespace std;
using namespace __gnu_pbds;

const int N = 1005;
int dis[N][N];

vector<pair<int,int>> adj[N];
gp_hash_table<string,int> mm;

int id = 1;

signed main(){
    fastio

    for(int i = 0;i < N;i++){
        for(int j = 0;j < N;j++){
            dis[i][j] = 1e18;
        }
    }


    int n,m;
    cin >> n >> m;
    for(int i = 0;i < m;i++){
        string a,b;
        int w;
        cin >> a >> b >> w;
        if(!mm[a]) mm[a] = id++;
        if(!mm[b]) mm[b] = id++;
        adj[mm[a]].push_back({mm[b],w});
    }

    for(int i = 1;i <= n;i++){
        std::priority_queue<pair<int,int>,vector<pair<int,int>>,greater<>> pq;
        dis[i][i] = 0;
        pq.push({0,i});
        while(!pq.empty()){
            auto [ww,u] = pq.top(); pq.pop();
            if(ww > dis[i][u]) continue;
            for(auto [v,w] : adj[u]){
                if(dis[i][v] > dis[i][u] + w){
                    dis[i][v] = dis[i][u] + w;
                    pq.push({dis[i][v],v});
                }
            } 
        }
    }

    int q;
    cin >> q;

    while(q--){
        string a,b;
        cin >> a >> b;
        int ans = dis[mm[a]][mm[b]];
        if(ans==1e18) cout << "Roger\n";
        else cout << ans << "\n";
    }
}

• Subtask 1: 70 / 70