Advertisement
skimono

For Tinkoff

Oct 9th, 2021
218
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.52 KB | None | 0 0
  1. #define _CRT_SECURE_NO_WARNINGS
  2. #include <iostream>
  3. #include <vector>
  4. #include <algorithm>
  5. #include <cmath>
  6. #include <stack>
  7. #include <iomanip>
  8. #include <fstream>
  9. #include <string>
  10. #include <set>
  11. #include <deque>
  12. #include <queue>
  13. #include <map>
  14. #include <bitset>
  15. #include <random>
  16.  
  17. using namespace std;
  18.  
  19. typedef long long ll;
  20. typedef unsigned long long ull;
  21. typedef long double ld;
  22. #define endl "\n"
  23. #define sqrt sqrtl
  24.  
  25. #define all(a) a.begin(), a.end();
  26.  
  27. const ll inf = 1e9 + 13;
  28. long double eps = 1e-6;
  29. const ll maxsz = 1e6 + 5;
  30. ll mod = 1e9 + 7;
  31.  
  32. vector <short> dfs(vector <set <short> >& g, short v, vector <bool>& u, vector <vector <bool> > &a) {
  33.     u[v] = true;
  34.     short i, j;
  35.     vector <short> n;
  36.     for (auto i = g[v].begin(); i != g[v].end(); i++) {
  37.         j = *i;
  38.         if (!u[j]) {
  39.             vector <short> x = dfs(g, j, u, a);
  40.             for (int y = 0; y < x.size(); y++) {
  41.                 n.push_back(x[y]);
  42.             }
  43.             n.push_back(j);
  44.         }
  45.     }
  46.     for (i = 0; i < n.size(); i++) {
  47.         //cout << n[i] << " ";
  48.         a[v][n[i]] = 1;
  49.     }
  50.     //cout << endl;
  51.     return n;
  52. }
  53.  
  54. signed main() {
  55. #ifdef _DEBUG
  56.     freopen("input.txt", "r", stdin);
  57.     freopen("output.txt", "w", stdout);
  58. #endif
  59.     ios_base::sync_with_stdio(0);
  60.     cin.tie(NULL);
  61.     cout.tie(NULL);
  62.     short n;
  63.     cin >> n;
  64.     short i, j, c1 = 0, c2 = 0;
  65.     vector <set <short> > gr(n), gb(n);
  66.     for (i = 0; i < n - 1; i++) {
  67.         string s;
  68.         cin >> s;
  69.         for (j = 0; j < s.size(); j++) {
  70.             if (s[j] == 'R') {
  71.                 c1++;
  72.                 gr[i].insert(j + i + 1);
  73.                 //gr[j + 1 + i].push_back(i);
  74.             }
  75.             else {
  76.                 c2++;
  77.                 gb[i].insert(j + i + 1);
  78.                 //gb[j + 1 + i].push_back(i);
  79.             }
  80.         }
  81.     }
  82.     vector <vector <bool> > a(n, vector <bool>(n));
  83.     vector <vector <bool> > b(n, vector <bool>(n));
  84.     vector <bool> u1(n);
  85.     vector <bool> u2(n);
  86.     for (i = 0; i < n; i++) {
  87.         if (!u1[i]) {
  88.             vector <short> gg = dfs(gr, i, u1, a);
  89.         }
  90.     }
  91.     for (i = 0; i < n; i++) {
  92.         if (!u2[i]) {
  93.             vector <short> gg = dfs(gb, i, u2, b);
  94.         }
  95.     }
  96.     for (i = 0; i < n; i++) {
  97.         for (j = i + 1; j < n; j++) {
  98.             if (a[i][j] == 1 && b[i][j] == 1) {
  99.                 cout << "NO" << endl;
  100.                 return 0;
  101.             }
  102.         }
  103.     }
  104.     cout << "YES" << endl;
  105.     return 0;
  106. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement