Advertisement
999ms

Untitled

Oct 23rd, 2021
153
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.69 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. #define all(x) begin(x), end(x)
  4.  
  5. using namespace std;
  6. using ll = long long;
  7.  
  8. map<string, int> mp;
  9.  
  10. int rs() {
  11. string s;
  12. cin >> s;
  13. if (mp.count(s)) return mp[s];
  14. return mp[s] = (int) mp.size();
  15. }
  16.  
  17. const int N = 303;
  18.  
  19. enum {
  20. UNDEF,
  21. PAR,
  22. NON
  23. };
  24.  
  25. int g[N][N];
  26.  
  27. bool par[N][N];
  28. bool notPar[N][N];
  29.  
  30.  
  31. void YES() {
  32. cout << "Yes\n";
  33. exit(0);
  34. }
  35.  
  36. void NO() {
  37. cout << "No\n";
  38. exit(0);
  39. }
  40.  
  41. void solve() {
  42. int f = rs();
  43. int t = rs();
  44. int n;
  45. cin >> n;
  46.  
  47. vector<int> from;
  48. vector<vector<pair<int, int>>> edges(n);
  49. map<pair<int, int>, vector<int>> indexes;
  50.  
  51. for (int i = 0; i < n; i++) {
  52. auto &v = edges[i];
  53. int k;
  54. cin >> k;
  55. v.resize(k);
  56. for (auto&[l, r]: v) {
  57. l = rs();
  58. r = rs();
  59. indexes[{l, r}].push_back(i);
  60. }
  61. }
  62.  
  63. if (indexes.count({f, t}) == 0) {
  64. YES();
  65. }
  66.  
  67. vector<bool> used(n);
  68. vector<int> q = indexes[{f, t}];
  69.  
  70. int sz = mp.size();
  71.  
  72. auto kek = [&](int x, int y) {
  73. auto &v = indexes[{x, y}];
  74. for (int i = 0; i < int(v.size()); i++) {
  75. if (!used[v[i]]) {
  76. q.push_back(v[i]);
  77. used[v[i]] = true;
  78. }
  79. }
  80. v.clear();
  81. };
  82.  
  83. auto relax = [&](vector<pair<int, int>> &e) {
  84. vector<pair<int, int>> cur, rev;
  85. for (auto[l, r]: e) {
  86. cur.emplace_back(r, l);
  87. rev.emplace_back(l, l);
  88. }
  89. for (int i = 0; i < int(cur.size()); i++) {
  90. auto[v, p] = cur[i];
  91. for (int to = 0; to < sz; to++) {
  92. if (g[v][to] == PAR && g[p][to] != PAR) {
  93. g[p][to] = PAR;
  94. kek(p, to);
  95. // p -> to
  96. cur.emplace_back(p, to);
  97. }
  98. }
  99. }
  100.  
  101. for (int i = 0; i < int(rev.size()); i++) {
  102. auto[p, c] = rev[i];
  103. for (int to = 0; to < sz; to++) {
  104. if (g[p][c] == PAR && g[to][c] != PAR) {
  105. g[to][c] = PAR;
  106. kek(to, c);
  107. rev.emplace_back(to, c);
  108. }
  109. }
  110. }
  111. };
  112.  
  113. for (int i = 0; i < int(q.size()); i++) {
  114. int v = q[i];
  115. if (used[v]) continue;
  116. used[v] = true;
  117. vector<pair<int, int>> e;
  118.  
  119. for (auto[x, y]: edges[v]) {
  120. if (g[x][y] == UNDEF) {
  121. g[x][y] = PAR;
  122. e.emplace_back(x, y);
  123. }
  124. }
  125. relax(e);
  126. }
  127.  
  128. for (int i = 0; i < sz; i++) {
  129. for (int j = 0; j < sz; j++) {
  130. if (g[i][j] == PAR && g[j][i] == PAR) {
  131. NO();
  132. }
  133. }
  134. }
  135.  
  136. for (int i = 0; i < n; i++) {
  137. if (!used[i]) {
  138. for (auto [l, r] : edges[i]) {
  139. if (g[l][r] == PAR) {
  140. NO();
  141. }
  142. }
  143. }
  144. }
  145.  
  146. YES();
  147. }
  148.  
  149. int main() {
  150. ios_base::sync_with_stdio(false);
  151. cin.tie(nullptr);
  152. solve();
  153. }
  154.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement