API tools faq
paste
Advertisement
tepyotin2

The Great Revegation

tepyotin2
Jul 6th, 2025
404
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.29 KB | None | 0 0
raw download clone embed print report
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. struct Con{
  6.     int to;
  7.     string s;
  8. };
  9.  
  10. int n, m;
  11. vector<vector<Con>> con;
  12. vector<int> color;
  13. bool check = false;
  14. int ans = 0;
  15.  
  16. void dfs(int x, int v){
  17.     color[x] = v;
  18.  
  19.     /*
  20.     Check the nodes that are connected to the current node.
  21.     If the connected node has been checked before, the value must be
  22.     equal if the relation of these nodes are same and the value must
  23.     be different if the relation of these nodes are supposed to be
  24.     different, otherwise the pastures according to the cows are not
  25.     possible and must return.
  26.     If not visited before, send the new node to do dfs for that new
  27.     node and make the value 1 or 2 according to whether the relation
  28.     between these nodes are same or different and whether the current
  29.     node has a value of 1 or 2.
  30.     */
  31.  
  32.     for(Con c: con[x]){
  33.         if(color[c.to] > 0){
  34.             // cout << "x: " << x << ", c.to: " << c.to << ", color[c.to]: " << color[c.to] << '\n';
  35.             if(c.s == "S" && color[c.to]!=v){
  36.                 check = true;
  37.                 return;
  38.             }else if(c.s == "D" && color[c.to]==v){
  39.                 check = true;
  40.                 return;
  41.             }
  42.         }else{
  43.             if(c.s == "S"){
  44.                 dfs(c.to, v);
  45.             }else if(c.s == "D"){
  46.                 if(v == 1){
  47.                     dfs(c.to, 2);
  48.                 }else{
  49.                     dfs(c.to, 1);
  50.                 }
  51.             }
  52.         }
  53.     }
  54. }
  55.  
  56. int main(){
  57.     freopen("revegetate.in", "r", stdin);
  58.     freopen("revegetate.out", "w", stdout);
  59.  
  60.     cin >> n >> m;
  61.     con.resize(n+1);
  62.     color.resize(n+1, 0);
  63.     for(int i=0; i<m; i++){
  64.         string s;
  65.         int a, b;
  66.         cin >> s >> a >> b;
  67.         con[a].push_back({b, s});
  68.         con[b].push_back({a, s});
  69.     }
  70.  
  71.     /*
  72.     Use for loop to find the groups by getting values that hasn't been
  73.     used before and sending to dfs function to get the group it is
  74.     connected to
  75.     */
  76.  
  77.     for(int i=1; i<=n; i++){
  78.         if(color[i] == 0){
  79.             dfs(i, 1);
  80.             if(check){
  81.                 // cout << "HI" << '\n';
  82.                 cout << 0 << '\n';
  83.                 return 0;
  84.             }else{
  85.                 // ans*=2;
  86.                 ans++;
  87.             }
  88.         }
  89.     }
  90.     // int len = (int)(log2(ans));
  91.     // cout << bitset<64>(ans).to_string().substr(64-ans-1) << '\n';
  92.     // string bi = "";
  93.     // while(ans>0){
  94.     //     int bit = ans%2;
  95.     //     bi.push_back('0'+bit);
  96.     //     ans/=2;
  97.     // }
  98.     // reverse(bi.begin(), bi.end());
  99.     // cout << bi << '\n';
  100.  
  101.     /*
  102.     The answer of this problem, if not 0, can only be a value that is 2
  103.     to the power of some number, for example (2, 4, 8, 16, 32, 64, etc.).
  104.     Since these values are all 10, 100, 1000, etc. with the amount of 0s
  105.     being the amount that 2 is being powered by, we could just output 1
  106.     and then 0 for the amount of times that the ans must be multiplied
  107.     by itself, becomes the answer. The functions or methods for turning
  108.     a number into binary value, as tried above would not work for this
  109.     problem.
  110.     */
  111.        
  112.     cout << "1";
  113.     for(int i=0; i<ans; i++){
  114.         cout << "0";
  115.     }
  116.     cout << '\n';
  117.  
  118.     return 0;
  119. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!