fork download
copy 
  1.  
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4. typedef long long int ll;
  5. #define pb push_back
  6. #define mp make_pair
  7. #define vc vector
  8. #define fs first
  9. #define sec second
  10. #define pll pair<ll,ll> 
  11.  
  12.  
  13. ll comp=1;
  14.  
  15.  
  16. struct vertex
  17. {
  18.     vc<pll> adj;
  19.     ll vis=0;
  20.     ll col=1;
  21.     ll component=0;
  22. };
  23.  
  24.  
  25. map<string,ll> m;
  26. set<ll> s1;
  27. bool flag=false;
  28.  
  29.  
  30. void dfs(struct vertex x[],ll sor)
  31. {
  32.     x[sor].vis=1;
  33.     x[sor].component=comp;
  34.     ll p=0;
  35.     if(x[sor].col==0)                       // if this statement is false, p=1
  36.         p=1;
  37.     for(auto y:x[sor].adj)
  38.         if(!x[y.fs].vis)
  39.         {
  40.             x[y.fs].col=(y.sec^p);          //(y.sec^p) gives the required colour of its neighbours
  41.             dfs(x,y.fs);
  42.         }
  43.         else if((y.sec^p)!=x[y.fs].col){    //if the node is already visited and does not have the required colour
  44.             flag=true;
  45.             s1.insert(x[sor].component);    // set s1 contains components where contradiction was found
  46.         }
  47.  
  48. }
  49.  
  50. int main() {
  51.     ios_base::sync_with_stdio(false);
  52.     cin.tie(0);cout.tie(0);
  53.  
  54.     m["true"]=1;                    // true is given colour 1 and flase is given 0.
  55.     m["false"]=0;
  56.  
  57.     while(1)
  58.     {
  59.         flag=false;
  60.         s1.clear();
  61.         ll n;
  62.         cin>>n;
  63.  
  64.         if(!n)
  65.             break;
  66.  
  67.         struct vertex x[n];             // assuming all statements to be true.
  68.  
  69.         for(ll a=0;a<n;a++)
  70.         {
  71.             ll u;
  72.             cin>>u;
  73.             u--;
  74.             string s;
  75.             cin>>s;
  76.             x[a].adj.pb(mp(u,m[s]));        // pair of (node,node_colour) where true is 1 and false is 0
  77.         }
  78.  
  79.         for(ll a=0;a<n;a++)
  80.             if(x[a].vis==0){
  81.                 dfs(x,a);                   // to find if there is contradiction in in itial assumption
  82.                 comp++;
  83.             }
  84.  
  85.         flag=false;                         // Global variables
  86.         comp=1;
  87.  
  88.         for(ll a=0;a<n;a++){
  89.             if(s1.count(x[a].component))    // If the set contains the component of the node 
  90.                 x[a].col=0;                 // this means contradiction was found
  91.             else                            // Since intial assumption was true
  92.                 x[a].col=1;                 // now initializing with false
  93.                                             // if set does not contain, true was assigned correctly
  94.  
  95.  
  96.             x[a].vis=0;                     // initializing variables of each node
  97.             x[a].component=0;
  98.         }
  99.  
  100.         s1.clear();
  101.  
  102.         for(ll a=0;a<n;a++)
  103.             if(x[a].vis==0){
  104.                 dfs(x,a);                   // Again DFS for finding if contradiction exists
  105.                 comp++;
  106.             }
  107.  
  108.         if(flag)                            // If flag is true then contradiction exists
  109.             cout<<"PARADOX\n";
  110.         else
  111.             cout<<"NOT PARADOX\n";
  112.     }
  113. 	return 0;
  114. }
Runtime error #stdin #stdout 0s 15240KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/tlbX3a
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!