Submission #415375

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
415375	2021-06-01T03:12:23 Z	sam571128	Alias (COCI21_alias)	C++17	70 / 70	12 ms	8524 KB

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.0 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	8244 KB	Output is correct
2	Correct	5 ms	8140 KB	Output is correct
3	Correct	9 ms	8340 KB	Output is correct
4	Correct	12 ms	8348 KB	Output is correct
5	Correct	11 ms	8504 KB	Output is correct
6	Correct	9 ms	8512 KB	Output is correct
7	Correct	7 ms	8524 KB	Output is correct