fork download 
  1. //BISMILLAHIRRAHMANIRRAHIM
  2. /*
  3.  manus tar shopner soman boro
  4.  Author :: Shakil Ahmed
  5. .............AUST_CSE27.........
  6.  prob   ::
  7.  Type   ::
  8.  verdict::
  9.  */
  10.  
  11. #include <bits/stdc++.h>
  12. #define pb push_back
  13. #define mp make_pair
  14. #define pi acos(-1.0)
  15. #define ff first
  16. #define ss second
  17. #define re return
  18. #define QI queue<int>
  19. #define SI stack<int>
  20. #define SZ(x) ((int) (x).size())
  21. #define all(x) (x).begin(), (x).end()
  22. #define sqr(x) ((x) * (x))
  23. #define memo(a,b) memset((a),(b),sizeof(a))
  24. #define G() getchar()
  25. #define MAX3(a,b,c) max(a,max(b,c))
  26.  
  27. double const EPS=3e-8;
  28. using namespace std;
  29.  
  30. #define FI freopen ("input.txt", "r", stdin)
  31. #define FO freopen ("output.txt", "w", stdout)
  32.  
  33. typedef long long Long;
  34. typedef long long int64;
  35. typedef unsigned long long ull;
  36. typedef vector<int> vi ;
  37. typedef set<int> si;
  38. typedef vector<Long>vl;
  39. typedef pair<int,int>pii;
  40. typedef pair<string,int>psi;
  41. typedef pair<Long,Long>pll;
  42. typedef pair<double,double>pdd;
  43. typedef vector<pii> vpii;
  44.  
  45. // For loop
  46.  
  47. #define forab(i, a, b)	for (__typeof (b) i = (a) ; i <= b ; ++i)
  48. #define rep(i, n)		forab (i, 0, (n) - 1)
  49. #define For(i, n)		forab (i, 1, n)
  50. #define rofba(i, a, b)	for (__typeof (b)i = (b) ; i >= a ; --i)
  51. #define per(i, n)		rofba (i, 0, (n) - 1)
  52. #define rof(i, n)		rofba (i, 1, n)
  53. #define forstl(i, s)	for (__typeof ((s).end ()) i = (s).begin (); i != (s).end (); ++i)
  54.  
  55. template< class T > T gcd(T a, T b) { return (b != 0 ? gcd<T>(b, a%b) : a); }
  56. template< class T > T lcm(T a, T b) { return (a / gcd<T>(a, b) * b); }
  57.  
  58. //Fast Reader
  59. template<class T>inline bool read(T &x){int c=getchar();int sgn=1;while(~c&&c<'0'||c>'9'){if(c=='-')sgn=-1;c=getchar();}for(x=0;~c&&'0'<=c&&c<='9';c=getchar())x=x*10+c-'0'; x*=sgn; return ~c;}
  60.  
  61. //int dx[]={1,0,-1,0};int dy[]={0,1,0,-1}; //4 Direction
  62. //int dx[]={1,1,0,-1,-1,-1,0,1};int dy[]={0,1,1,1,0,-1,-1,-1};//8 direction
  63. //int dx[]={2,1,-1,-2,-2,-1,1,2};int dy[]={1,2,2,1,-1,-2,-2,-1};//Knight Direction
  64. //int dx[]={2,1,-1,-2,-1,1};int dy[]={0,1,1,0,-1,-1}; //Hexagonal Direction
  65.  
  66. /* **************************************  My code start here ****************************************** */
  67. const int MX = 2000000 + 5 ;
  68. vector < pii > g[MX];
  69. vector <int> Adj[MX];
  70. int n , m , color[MX] , vis , col[2] ;
  71.  
  72. void ini()
  73. {
  74.     int i ;
  75.     for ( i = 0 ; i <= n ; i++ )
  76.     {
  77.         g[i].clear();
  78.         Adj[i].clear();
  79.         color[i] = -1; // haven't updated yet
  80.     }
  81. }
  82. bool dfs(int x , int c,int par)
  83. {
  84.     color[x] = c ;
  85.     col[c]++;
  86.     int sz = Adj[x].size();
  87.     for ( int i = 0 ; i < sz ; i++ )
  88.     {
  89.         int u = Adj[x][i];
  90.         if( par == u ) continue ;
  91.         if( color[u] == -1 && !dfs(u,!c,x)) return 0;
  92.         else
  93.         {
  94.             if( color[u] == c ) return 0;
  95.         }
  96.     }
  97.     return 1 ;
  98. }
  99. bool ok(int x , int col)
  100. {
  101.     // here col is fixed color
  102. }
  103. int main()
  104. {
  105.    // ios_base::sync_with_stdio(0); cin.tie(0);
  106.  
  107.     while(scanf("%d %d",&n,&m)==2)
  108.     {
  109.         map < int , int > VIS ;
  110.         int u , v , c , i ;
  111.         ini();
  112.         bool ok = 1 ;
  113.         for ( i = 0 ; i < m ; i++ )
  114.         {
  115.             cin >> u >> v >> c ;
  116.  
  117.             if( c == 0 && ( color[u] == 1 || color[v] == 1 ) ) // As its 0 , its adjacent should be also zero
  118.             {
  119.                 ok = 0 ;
  120.             }
  121.             else if( c == 0  )
  122.             {
  123.                 color[u] = 0 ;
  124.                 color[v] = 0 ;
  125.             }
  126.             else if( c == 2 && ( color[u] == 0 || color[v] == 0 ) ) // As its 1 , its Adjacent must be 1
  127.             {
  128.                 ok = 0 ;
  129.             }
  130.             else if( c == 2 )
  131.             {
  132.  
  133.                 color[u] = 1 ;
  134.                 color[v] = 1 ;
  135.             }
  136.             g[u].pb(mp(v,c));
  137.             g[v].pb(mp(u,c));
  138.         }
  139.  
  140.         // 1st part is complete now i calculate all number 1 color vertex and
  141.         // try to check bi-coloring between those who has -1 coloring
  142.  
  143.         for (int i = 1 ; i <= n && ok ; i++ )
  144.         {
  145.  
  146.             if ( color[i] == 1 )
  147.             {
  148.                 // As its 1  all vextexes connected with it 1 , must be 1
  149.                 // or connected with it by -1 must be 0
  150.                 int sz = g[i].size();
  151.                 int x ;
  152.                 for( x = 0 ; x < sz ; x++ )
  153.                 {
  154.                     int c = g[i][x].second ;
  155.                     int v = g[i][x].first ;
  156.                     if ( c == 2 && color[v] == 0 )
  157.                     {
  158.                         ok = 0 ; // conflict as it both the node should be 1
  159.                     }
  160.                     else if( c == 1 && color[v] == -1 )
  161.                     {
  162.                         color[v] = 0 ; // it must be 0
  163.                     }
  164.                     else
  165.                     {
  166.                         // c is 0 it can't be possible
  167.                         ok = 0 ;
  168.                     }
  169.                 }
  170.             }
  171.             else if( color[i] == 0 )
  172.             {
  173.                  // As its 0  all vextexes connected with it 1 , must be 0
  174.                 // or connected with it by -1 must be 1 if c is 1
  175.                 int sz = g[i].size();
  176.                 int x ;
  177.                 for( x = 0 ; x < sz ; x++ )
  178.                 {
  179.                     int c = g[i][x].second ;
  180.                     int v = g[i][x].first ;
  181.                     if ( c == 0 && color[v] == 1 )
  182.                     {
  183.                         ok = 0 ; // conflict as it both the node should be 0
  184.                     }
  185.                     else if( c == 1 && color[v] == -1 )
  186.                     {
  187.                         color[v] = 1 ; // it must be 0
  188.                     }
  189.                     else
  190.                     {
  191.                         // c is 2 it can't be possible
  192.                         ok = 0 ;
  193.                     }
  194.                 }
  195.             }
  196.         }
  197.         if( !ok ) // its not possible satisfied all equation
  198.         {
  199.             puts("impossible");
  200.             continue;
  201.         }
  202.         int Ans = 0 , sum = 0 ;
  203.         // Now construct a bi-coloring graph where both end vectex color is write now -1 ;
  204.         int idx = 0 ;
  205.         for ( int i = 1 ; i <= n ; i++ )
  206.         {
  207.  
  208.             if( color[i] == 1 ) // here must be a lounch
  209.             Ans++;
  210.             else if( color[i] == -1)
  211.             {
  212.                 if( VIS.find(i) == VIS.end() )
  213.                 {
  214.                     VIS[i] = ++idx ;
  215.                 }
  216.                 int sz  = g[i].size();
  217.                 int x , y , z ;
  218.                 x = VIS[i];
  219.                 for (  z = 0 ; z < sz ; z++ )
  220.                 {
  221.                     int v = g[i][z].first ;
  222.                     y  = v ;
  223.                     int c = g[i][z].second;
  224.                     if( VIS.find(v) == VIS.end() )
  225.                     {
  226.                         VIS[v] = ++idx ;
  227.                     }
  228.                     y = VIS[v];
  229.                     if( c == 1 &&  color[v] == -1 ) // there must be a edge in bi_coloring graph
  230.                     {
  231.                         Adj[x].pb(y);
  232.                     }
  233.                 }
  234.             }
  235.         }
  236.         for (int i = 1 ; i <= idx && ok ; i++ )
  237.         {
  238.             if( color[i] == -1 )
  239.             {
  240.                 col[0] = col[1] = 0 ;
  241.                 ok = dfs(i,1,-1);
  242.                 Ans += min(col[0],col[1]);
  243.             }
  244.         }
  245.          if( !ok ) // its not possible satisfied all equation
  246.         {
  247.             puts("impossible");
  248.             continue;
  249.         }
  250.         else
  251.         {
  252.             cout << Ans << endl ;
  253.         }
  254.  
  255.     }
  256.  
  257.  
  258.  
  259.     return 0;
  260. }
  261.  
Success #stdin #stdout 0.05s 58032KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/SngwiE
language:
C++ (gcc 8.3)
created:
9 years ago
visibility:
public

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!