Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #define _CRT_SECURE_NO_WARNINGS
- #include <iostream>
- #include <vector>
- #include <string>
- #include <map>
- #include <algorithm>
- #define inf 40
- #define mod 27644437
- using namespace std;
- long long f(map<string, long long>& m, string key)
- {
- if (m.find(key) == m.end())
- {
- m[key] = m.size();
- return m.size() - 1;
- }
- else
- return m[key];
- }
- void get_graph(long long n, vector<vector<long long> >& v, map<string, long long>& m, map<long long, string>& mi)
- {
- string a, b;
- for (long long i = 0; i < n; i++)
- {
- cin >> a >> b;
- long long ia = f(m, a);
- mi[ia] = a;
- long long ib = f(m, b);
- mi[ib] = b;
- v[ia][ib] = 1;
- v[ia][ia] = 0;
- v[ib][ib] = 0;
- }
- }
- void get_path(vector<vector<long long> >& v)
- {
- for (long long k = 0; k < v.size(); k++)
- {
- for (long long i = 0; i < v.size(); i++)
- for (long long j = 0; j < v.size(); j++)
- v[i][j] = min(v[i][j], v[i][k] + v[k][j]);
- }
- }
- long long mul(long long a, long long b)
- {
- return (a*b) % (mod);
- }
- vector<vector<long long> > mult(const vector<vector<long long> >& a, const vector<vector<long long> >& b)
- {
- vector<vector<long long> > v(a.size(), vector<long long>(b[0].size()));
- for (long long i = 0; i < a.size(); i++)
- for (long long j = 0; j < b[0].size(); j++)
- for (long long k = 0; k < a[0].size(); k++)
- v[i][j] = ((mul(a[i][k], b[k][j]) + v[i][j])) % mod;
- return v;
- }
- vector<vector<long long> > pow(const vector<vector<long long> >& v, long long p)
- {
- if (p == 0)
- {
- vector<vector<long long> > pp(v.size(), vector<long long>(v.size()));
- for (long long i = 0; i < pp.size(); i++)
- pp[i][i] = 1;
- return pp;
- }
- if (p == 1)
- return v;
- if (p % 2 == 1)
- return mult(pow(v, p - 1), v);
- else
- return pow(mult(v, v), p / 2);
- }
- void print(vector<vector<long long> >& a)
- {
- for (int i = 0; i < a.size(); i++)
- {
- for (int j = 0; j < a[0].size(); j++)
- cout << a[i][j] << " ";
- cout << endl;
- }
- cout << endl;
- cout << endl;
- }
- int main()
- {
- //ios_base::sync_with_stdio(0);
- //freopen("input.txt", "r", stdin);
- //freopen("output.txt", "w", stdout);
- long long n;
- cin >> n;
- int ppp = 1;
- while (n != 0)
- {
- if (ppp != 1)
- cout << endl;
- vector<vector<long long> > a(2 * n, vector<long long>(2 * n, inf)), b(2 * n, vector<long long>(2 * n, inf));
- vector<vector<long long> > aa(2 * n, vector<long long>(2 * n, inf)), bb(2 * n, vector<long long>(2 * n, inf));
- map<string, long long> ma, mb;
- map<long long, string> mai, mbi;
- get_graph(n, a, ma, mai);
- get_graph(n, b, mb, mbi);
- aa = a;
- bb = b;
- for (int i = 0; i < aa.size(); i++)
- {
- for (int j = i + 1; j < aa.size(); j++)
- swap(aa[i][j], aa[j][i]);
- sort(aa[i].begin(), aa[i].end());
- }
- for (int i = 0; i < bb.size(); i++)
- {
- for (int j = i + 1; j < bb.size(); j++)
- swap(bb[i][j], bb[j][i]);
- sort(bb[i].begin(), bb[i].end());
- }
- /*for (int i = 0; i < aa.size(); i++)
- sort(aa[i].begin(), aa[i].end());
- for (int i = 0; i < bb.size(); i++)
- sort(bb[i].begin(), bb[i].end());
- */
- get_path(a);
- get_path(b);
- a = pow(a, 51);
- b = pow(b, 51);
- vector<vector<long long> > ra(2 * n, vector<long long>(1)), rb(2 * n, vector<long long>(1));
- vector < vector<long long> > t1(2 * n, vector<long long>(1, 1));
- vector < vector<long long> > t2(2 * n, vector<long long>(1, 1));
- ra = mult(a, t1);
- rb = mult(b, t2);
- vector<pair<string, string> > s;
- for (int i = 0; i < ma.size(); i++)
- {
- for (int j = 0; j < mb.size(); j++)
- if (ra[i][0] == rb[j][0] && aa[i] == bb[j])
- {
- s.push_back(make_pair(mai[i], mbi[j]));
- break;
- }
- }
- sort(s.begin(), s.end());
- for (int i = 0; i < s.size(); i++)
- cout << s[i].first << "/" << s[i].second << endl;
- cin >> n;
- ppp++;
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement