oj.uz

Submission #948198

# Submission time Handle Problem Language Result Execution time Memory
948198 2024-03-17T20:53:21 Z shezitt Alias (COCI21_alias) C++14
70 / 70
 283 ms 972 KB 
#include <bits/stdc++.h>

using namespace std;

using ld = long double;
using ll = long long;

#define int ll

#define sz(x) (int)x.size()

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n, m;
    cin >> n >> m;

    map<string,vector<pair<string,int>>> adj;

    for(int i=0; i<m; ++i){
        string u, v;
        int w;
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
    }

    map<string,int> dis;

    auto bfs = [&](string u) -> void {
        dis.clear();
        priority_queue<pair<int,string>, vector<pair<int,string>>, greater<pair<int,string>>> pq;
        pq.push({0, u});
        dis[u] = 0;
        while(sz(pq)){
            auto [curCost, curNode] = pq.top();
            pq.pop();

            if(curCost != dis[curNode]) continue;

            for(auto [toNode, toCost] : adj[curNode]){
                if(dis.count(toNode) == 0 or curCost + toCost < dis[toNode]){
                    dis[toNode] = curCost + toCost;
                    pq.push({dis[toNode], toNode});
                }
            }
        }
    };

    int q;
    cin >> q;
    while(q--){
        string u, v;
        cin >> u >> v;

        bfs(u);

        if(dis.count(v) == 0){
            cout << "Roger" << endl;
        } else {
            cout << dis[v] << endl;
        }

    }

}

Compilation message

alias.cpp: In lambda function:
alias.cpp:37:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   37 |             auto [curCost, curNode] = pq.top();
      |                  ^
alias.cpp:42:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   42 |             for(auto [toNode, toCost] : adj[curNode]){
      |                      ^

Subtask #1
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 198 ms 648 KB Output is correct
4 Correct 283 ms 652 KB Output is correct
5 Correct 6 ms 604 KB Output is correct
6 Correct 6 ms 468 KB Output is correct
7 Correct 4 ms 972 KB Output is correct