Advertisement
Guest User

Untitled

a guest
Feb 7th, 2016
59
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.79 KB | None | 0 0
  1. #define _CRT_SECURE_NO_WARNINGS
  2. #include <iostream>
  3. #include <vector>
  4. #include <string>
  5. #include <map>
  6. #include <algorithm>
  7. #define inf 40
  8. #define mod 27644437
  9.  
  10. using namespace std;
  11.  
  12. long long f(map<string, long long>& m, string key)
  13. {
  14.     if (m.find(key) == m.end())
  15.     {
  16.         m[key] = m.size();
  17.         return m.size() - 1;
  18.     }
  19.     else
  20.         return m[key];
  21. }
  22.  
  23. void get_graph(long long n, vector<vector<long long> >& v, map<string, long long>& m, map<long long, string>& mi)
  24. {
  25.     string a, b;
  26.     for (long long i = 0; i < n; i++)
  27.     {
  28.         cin >> a >> b;
  29.         long long ia = f(m, a);
  30.         mi[ia] = a;
  31.         long long ib = f(m, b);
  32.         mi[ib] = b;
  33.         v[ia][ib] = 1;
  34.         v[ia][ia] = 0;
  35.         v[ib][ib] = 0;
  36.  
  37.     }
  38. }
  39.  
  40. void get_path(vector<vector<long long> >& v)
  41. {
  42.     for (long long k = 0; k < v.size(); k++)
  43.     {
  44.         for (long long i = 0; i < v.size(); i++)
  45.             for (long long j = 0; j < v.size(); j++)
  46.                 v[i][j] = min(v[i][j], v[i][k] + v[k][j]);
  47.     }
  48. }
  49.  
  50.  
  51. long long mul(long long a, long long b)
  52. {
  53.     return (a*b) % (mod);
  54. }
  55.  
  56. vector<vector<long long> > mult(const vector<vector<long long> >& a, const vector<vector<long long> >& b)
  57. {
  58.     vector<vector<long long> > v(a.size(), vector<long long>(b[0].size()));
  59.     for (long long i = 0; i < a.size(); i++)
  60.         for (long long j = 0; j < b[0].size(); j++)
  61.             for (long long k = 0; k < a[0].size(); k++)
  62.                 v[i][j] = ((mul(a[i][k], b[k][j]) + v[i][j])) % mod;
  63.     return v;
  64. }
  65.  
  66. vector<vector<long long> > pow(const vector<vector<long long> >& v, long long p)
  67. {
  68.     if (p == 0)
  69.     {
  70.         vector<vector<long long> > pp(v.size(), vector<long long>(v.size()));
  71.         for (long long i = 0; i < pp.size(); i++)
  72.             pp[i][i] = 1;
  73.  
  74.         return pp;
  75.     }
  76.     if (p == 1)
  77.         return v;
  78.     if (p % 2 == 1)
  79.         return mult(pow(v, p - 1), v);
  80.     else
  81.         return pow(mult(v, v), p / 2);
  82. }
  83.  
  84. void print(vector<vector<long long> >& a)
  85. {
  86.     for (int i = 0; i < a.size(); i++)
  87.     {
  88.         for (int j = 0; j < a[0].size(); j++)
  89.             cout << a[i][j] << " ";
  90.         cout << endl;
  91.     }
  92.     cout << endl;
  93.     cout << endl;
  94. }
  95.  
  96. int main()
  97. {
  98.     //ios_base::sync_with_stdio(0);
  99.     //freopen("input.txt", "r", stdin);
  100.     //freopen("output.txt", "w", stdout);
  101.  
  102.     long long n;
  103.     cin >> n;
  104.     int ppp = 1;
  105.     while (n != 0)
  106.     {
  107.         if (ppp != 1)
  108.             cout << endl;
  109.         vector<vector<long long> > a(2 * n, vector<long long>(2 * n, inf)), b(2 * n, vector<long long>(2 * n, inf));
  110.         vector<vector<long long> > aa(2 * n, vector<long long>(2 * n, inf)), bb(2 * n, vector<long long>(2 * n, inf));
  111.         map<string, long long> ma, mb;
  112.         map<long long, string> mai, mbi;
  113.  
  114.         get_graph(n, a, ma, mai);
  115.         get_graph(n, b, mb, mbi);
  116.  
  117.         aa = a;
  118.         bb = b;
  119.  
  120.         for (int i = 0; i < aa.size(); i++)
  121.         {
  122.             for (int j = i + 1; j < aa.size(); j++)
  123.                 swap(aa[i][j], aa[j][i]);
  124.             sort(aa[i].begin(), aa[i].end());
  125.         }
  126.  
  127.         for (int i = 0; i < bb.size(); i++)
  128.         {
  129.             for (int j = i + 1; j < bb.size(); j++)
  130.                 swap(bb[i][j], bb[j][i]);
  131.  
  132.             sort(bb[i].begin(), bb[i].end());
  133.         }
  134.  
  135.         /*for (int i = 0; i < aa.size(); i++)
  136.             sort(aa[i].begin(), aa[i].end());
  137.  
  138.         for (int i = 0; i < bb.size(); i++)
  139.             sort(bb[i].begin(), bb[i].end());
  140.     */
  141.         get_path(a);
  142.         get_path(b);
  143.  
  144.         a = pow(a, 51);
  145.         b = pow(b, 51);
  146.  
  147.         vector<vector<long long> > ra(2 * n, vector<long long>(1)), rb(2 * n, vector<long long>(1));
  148.         vector < vector<long long> > t1(2 * n, vector<long long>(1, 1));
  149.         vector < vector<long long> > t2(2 * n, vector<long long>(1, 1));
  150.  
  151.         ra = mult(a, t1);
  152.         rb = mult(b, t2);
  153.  
  154.         vector<pair<string, string> > s;
  155.  
  156.         for (int i = 0; i < ma.size(); i++)
  157.         {
  158.             for (int j = 0; j < mb.size(); j++)
  159.                 if (ra[i][0] == rb[j][0] && aa[i] == bb[j])
  160.                 {
  161.                     s.push_back(make_pair(mai[i], mbi[j]));
  162.                     break;
  163.                 }
  164.         }
  165.  
  166.         sort(s.begin(), s.end());
  167.         for (int i = 0; i < s.size(); i++)
  168.             cout << s[i].first << "/" << s[i].second << endl;
  169.         cin >> n;
  170.         ppp++;
  171.     }
  172.     return 0;
  173. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement