jane street swe inter

#include <bits/stdc++.h>
using namespace std;
using Fact = tuple<string, double, string>;
using Query = tuple<double, string, string>;
using Edge = pair<int, double>;
using UMapStrToInt = unordered_map<string, int>;
using Graph = vector<list<Edge>>;
using Answer = pair<double, bool>;

void computeIds(const vector<Fact> &facts, UMapStrToInt &idOfUnit) {
    int id = 0;
    for (const Fact &fact : facts) {
        string unit1 = get<0>(fact);
        string unit2 = get<2>(fact);
        if (!idOfUnit.count(unit1)) idOfUnit[unit1] = id++;
        if (!idOfUnit.count(unit2)) idOfUnit[unit2] = id++;
    }
}

void parseFacts(const vector<Fact> &facts, Graph &graph, UMapStrToInt idOfUnit) {
    graph.resize(idOfUnit.size());
    for (const Fact &fact : facts) {
        string unit1 = get<0>(fact);
        string unit2 = get<2>(fact);
        int id1 = idOfUnit[unit1];
        int id2 = idOfUnit[unit2];
        double w = get<1>(fact);
        graph[id1].push_back(make_pair(id2, w));
        graph[id2].push_back(make_pair(id1, 1. / w));
    }
}

bool dfs(const Graph &graph, int node, double curr, vector<bool> &vis, const int target, double &ans) {
    if (node == target) {
        ans = curr;
        return true;
    }
    bool ok = false;
    for (const Edge &e : graph[node]) {
        if (vis[e.first]) {
            continue;
        }
        vis[e.first] = true;
        ok |= dfs(graph, e.first, e.second * curr, vis, target, ans);
    }
    return ok;
}

double answerQuery(const Graph &graph, const UMapStrToInt &idOfUnit, const Query &q) {
    vector<bool> vis(graph.size());
    string unitFrom = get<1>(q);
    string unitTo = get<2>(q);
    int start = idOfUnit.at(unitFrom);
    int target = idOfUnit.at(unitTo);
    double ans;
    bool ok = dfs(graph, start, 1, vis, target, ans);
    if (!ok) {
        throw runtime_error("CANT_CONVERT");
    }
    return get<0>(q) * ans;
}

vector<Answer> answerQueries(const vector<Fact> &facts, const vector<Query> &queries) {
    UMapStrToInt idOfUnit;
    computeIds(facts, idOfUnit);
    Graph graph;
    parseFacts(facts, graph, idOfUnit);
    vector<Answer> ans;
    ans.reserve(queries.size());
    for (const Query &q: queries) {
        try {
            ans.emplace_back(answerQuery(graph, idOfUnit, q), true);
        } catch (const runtime_error& re) {
            //cerr << re.what() << endl;
            ans.emplace_back(.0, false);
        }
    }
    return ans;
}

int main() {
    const vector<Fact> facts = {
        make_tuple("m", 3.28, "ft"),
        make_tuple("ft", 12, "in"),
        make_tuple("hr", 60, "min"),
        make_tuple("min", 60, "sec"),
    };
    const vector<Query> queries = {
        make_tuple(2, "m", "in"),
        make_tuple(13, "in", "m"),
        make_tuple(2, "in", "hr"),
    };
    const auto ans = answerQueries(facts, queries);
    cout << fixed << setprecision(3);
    for (size_t i = 0; i < ans.size(); i++) {
        auto q = queries[i];
        if (ans[i].second) {
            cout << get<0>(q) << get<1>(q) << " = "
                << ans[i].first << ' ' << get<2>(q) << endl;
        } else {
            cout << get<0>(q) << get<1>(q)
             << " = CAN_NOT_CONVERT_TO " << get<2>(q) << endl;
        }
    }

    return 0;
}