fork download 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. using dvec = vector<double>;
  5. using svec = vector<string>;
  6. using smat = vector<svec>;
  7.  
  8. class Solution {
  9.     class vars_map: public unordered_map<string,int> {
  10.         inline void add(const string& name) {
  11.             if (find(name) == end())
  12.                 emplace(name,size()); }
  13.     public:
  14.         inline vars_map(const smat& equations) {
  15.             for (auto eq: equations)
  16.                 for (int i = 0; i < 2; ++i)
  17.                     add(eq[i]); }
  18.         inline int code(const string& name) const {
  19.             const auto it = find(name);
  20.             return it == end() ? -1 : it->second; } };
  21. 	using idpair = pair<int,double>;
  22. 	using idpvec = vector<idpair>;
  23. 	using idpmat = vector<idpvec>;
  24.     class graph: idpmat {
  25.     	using bvec = vector<bool>;
  26.         double compute(int u, int dest, bvec& visited, double ans) const {
  27.             if (visited[u] = true, dest == u)
  28.                 return ans;
  29.             for (auto [v,w]: at(u))
  30.                 if (visited[v])
  31.                     continue;
  32.                 else {
  33.                     const auto a = compute(v,dest,visited,ans*w);
  34.                     if (a != -1.0)
  35.                         return a; }
  36.             visited[u] = false;
  37.             return -1.0; }
  38.     public:
  39.         inline graph(smat& equations, dvec& values, vars_map& var) :
  40.             idpmat(var.size()) {
  41.             for (int m = values.size(), i = 0; i < m; ++i) {
  42.                 const auto& eq = equations[i];
  43.                 const auto val = values[i];
  44.                 const auto A = var[eq[0]];
  45.                 const auto B = var[eq[1]];
  46.                 at(A).emplace_back(B,1.0/val);
  47.                 at(B).emplace_back(A,val); } }
  48.         inline double compute(int src, int dest) const {
  49.             if (src == -1 or dest == -1)
  50.                 return -1.0;
  51.             bvec visited(size(),false);
  52.             return compute(src,dest,visited,1.0); } };
  53. public:
  54.     inline dvec calcEquation(smat& equations, dvec& values, smat& queries) {
  55.         vars_map var(equations);
  56.         const graph g(equations,values,var);
  57.         dvec ans;
  58.         for (auto s: queries)
  59.             ans.push_back(g.compute(var.code(s[1]),var.code(s[0])));
  60.         return ans; } };
  61.  
  62. int main() {
  63.     const int P = 2;
  64.     int N, Q; cin.tie(nullptr)->sync_with_stdio(false), cin >> N >> Q;
  65.     smat equation(N,svec(P)), query(Q,svec(P));
  66.     dvec value(N);
  67.     for (int i = 0; i < N; ++i)
  68.         cin >> equation[i][0] >> equation[i][1] >> value[i];
  69.     for (int i = 0; i < Q; ++i)
  70.         cin >> query[i][0] >> query[i][1];
  71.     cout << fixed << setprecision(5);
  72.     for (auto ans: Solution().calcEquation(equation,value,query))
  73.         cout << ans << ' ';
  74.     return 0; }
  75.  
Success #stdin #stdout 0.01s 5516KB
comments (?)
stdin 
3 4
a b 1.5
b c 2.5
bc cd 5.0
a c 
c b
bc cd
cd bc
stdout 
3.75000 0.40000 5.00000 0.20000
https://ideone.com/Z1tUjw
399. Evaluate Division
language:
C++14 (gcc 8.3)
created:
3 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!