fork download
copy 
  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. int n , m , need[MX];
  69. int C[3];
  70. struct abc
  71. {
  72.     int x , y , c ;
  73. }inp[MX];
  74. vector <int> g[MX] ;
  75. int  col[MX];
  76. /*
  77. int DP(int node,int isgurd,int par)
  78. {
  79.     if(vis[node][isgurd] ) return dp[node][isgurd];
  80.     vis[node][isgurd] = 1 ;
  81.     col[node] = 1 ;
  82.     int i , sz = g[node].size();
  83.     int sum = 0 ;
  84.     for ( i = 0 ; i < sz ; i++ )
  85.     {
  86.         int v = g[node][i];
  87.         if( v != par )
  88.         {
  89.             if(!isgurd) sum += DP(v,1,node);
  90.             else sum += min(DP(v,0,node),DP(v,1,node));
  91.         }
  92.     }
  93.     return dp[node][isgurd] = sum + isgurd ;
  94. } */
  95. bool dfs(int node,int c)
  96. {
  97.     queue < int > q ;
  98.     q.push(node);
  99.     col[node] = c ;
  100.     while(!q.empty())
  101.     {
  102.         int frnt = q.front();
  103.         C[col[frnt]]++;
  104.         q.pop();
  105.         int sz = g[frnt].size();
  106.         int i , v ;
  107.         for ( i = 0 ; i < sz ; i++ )
  108.         {
  109.             v = g[frnt][i];
  110.             if( col[v] == -1 )
  111.             {
  112.                 col[v] = !col[frnt];
  113.                 q.push(v);
  114.             }
  115.             else if ( col[v] == col[frnt] ) return 0 ;
  116.         }
  117.     }
  118.     return 1 ;
  119.  
  120. }
  121. void ini()
  122. {
  123.     int i ;
  124.     for ( int i = 0 ; i <= n+1 ; i++ ) { g[i].clear();
  125.     need[i] = -1 ; // no update yet
  126.  
  127.     col[i]  = -1 ;
  128.     }
  129. }
  130. int main()
  131. {
  132.    // ios_base::sync_with_stdio(0); cin.tie(0);
  133.  
  134.     while(scanf("%d %d",&n,&m)==2)
  135.     {
  136.         map < int , int > Mark;
  137.         int idx = 0 ;
  138.       ini();
  139.       int x , y , c ;
  140.       bool ok = 1;
  141.        set <int> ans ;
  142.       rep(i,m)
  143.       {
  144.           read(inp[i].x) ;
  145.           read(inp[i].y);
  146.           read(inp[i].c);
  147.           if( inp[i].c == 2 && (need[inp[i].x] == 0 || need[inp[i].y] == 0 ) )
  148.           {
  149.               //printf("edge :: %d need[inp[i].x] :: %d need[y]::%d\n2", i,need[inp[i].x],need[inp[i].y]);
  150.               ok = 0 ;
  151.           }
  152.           else if( inp[i].c == 2 )
  153.           {
  154.               need[inp[i].x] = 1 ;
  155.               need[inp[i].y] = 1 ;
  156.               ans.insert(inp[i].x);
  157.               ans.insert(inp[i].y);
  158.           }
  159.           if( inp[i].c == 0 && ( need[inp[i].x] == 1  || need[inp[i].y] == 1) )
  160.           {
  161.  
  162.               ok = 0 ;
  163.           }
  164.           else if( inp[i].c == 0 )
  165.           {
  166.               need[inp[i].x] = 0 ;
  167.               need[inp[i].x] = 0 ;
  168.           }
  169.       }
  170.       if(!ok)
  171.       {
  172.           puts("impossible");
  173.           continue;
  174.       }
  175.  
  176.       rep(i,m)
  177.       {
  178.              if( inp[i].c == 2 && (need[inp[i].x] == 0 || need[inp[i].y] == 0 ) )
  179.           {
  180.               //printf("edge :: %d need[inp[i].x] :: %d need[y]::%d\n2", i,need[inp[i].x],need[inp[i].y]);
  181.               ok = 0 ;
  182.           }
  183.             if( inp[i].c == 0 && ( need[inp[i].x] == 1  || need[inp[i].y] == 1) )
  184.           {
  185.  
  186.               ok = 0 ;
  187.           }
  188.           if(!ok ) break;
  189.           if(inp[i].c == 2 || inp[i].c == 0 ) continue;
  190.           if( need[inp[i].x] == 0 && need[inp[i].y] == 0 )
  191.           {ok = 0 ; // printf("edge :: %d",i);
  192.          // printf("inp[i].x :: %d need :: %d inp[i].y :: %d need :: %d\n",inp[i].x,need[inp[i].x],inp[i].y,need[inp[i].y]);
  193.           }
  194.           else if( need[inp[i].x] == 1 && need[inp[i].y] == 1 )
  195.           { ok = 0 ;
  196.        //   printf("edge:: %d\n",i);
  197.         //   printf("inp[i].x :: %d need :: %d inp[i].y :: %d need :: %d\n",inp[i].x,need[inp[i].x],inp[i].y,need[inp[i].y]);
  198.            // ans.insert(inp[i].x); // 2i khanei bosathe hobe tai
  199.            // ans.insert(inp[i].y);
  200.           }
  201.           else if( (need[inp[i].x] == 1 && need[inp[i].y] == -1) || (need[inp[i].x] ==-1 && need[inp[i].y] == 1 ) )
  202.           {
  203.               if(need[inp[i].x] == 1 )
  204.               {
  205.                   ans.insert(inp[i].x);
  206.               }
  207.               else ans.insert(inp[i].y);
  208.           }
  209.              else if( (need[inp[i].x] == 0 && need[inp[i].y] == -1) || (need[inp[i].x] ==-1 && need[inp[i].y] == 0 ) )
  210.           {
  211.               if(need[inp[i].x] == -1 )
  212.               {
  213.                   ans.insert(inp[i].x);
  214.               }
  215.               else ans.insert(inp[i].y);
  216.           }
  217.           else {
  218.             if(Mark[inp[i].x] == 0 ) Mark[inp[i].x] = ++idx;
  219.             if(Mark[inp[i].y] == 0 ) Mark[inp[i].y] = ++idx;
  220.             int _x = Mark[inp[i].x] ;
  221.             int _y = Mark[inp[i].y];
  222.  
  223.           g[_x].pb(_y);
  224.           g[_y].pb(_x);
  225.           }
  226.           if( !ok ) break;
  227.  
  228.  
  229.       }
  230.         if(!ok)
  231.       {
  232.           puts("impossible");
  233.           continue;
  234.       }
  235.       rep(i,m)
  236.       {
  237.               if( inp[i].c == 2 && (need[inp[i].x] == 0 || need[inp[i].y] == 0 ) )
  238.           {
  239.               //printf("edge :: %d need[inp[i].x] :: %d need[y]::%d\n2", i,need[inp[i].x],need[inp[i].y]);
  240.               ok = 0 ;
  241.           }
  242.             if( inp[i].c == 0 && ( need[inp[i].x] == 1  || need[inp[i].y] == 1) )
  243.           {
  244.  
  245.               ok = 0 ;
  246.           }
  247.           if(!ok ) break;
  248.           if(inp[i].c == 2 || inp[i].c == 0 ) continue;
  249.           if( need[inp[i].x] == 0 && need[inp[i].y] == 0 )
  250.           {ok = 0 ; // printf("edge :: %d",i);
  251.          // printf("inp[i].x :: %d need :: %d inp[i].y :: %d need :: %d\n",inp[i].x,need[inp[i].x],inp[i].y,need[inp[i].y]);
  252.           }
  253.           else if( need[inp[i].x] == 1 && need[inp[i].y] == 1 )
  254.           { ok = 0 ;
  255.        //   printf("edge:: %d\n",i);
  256.         //   printf("inp[i].x :: %d need :: %d inp[i].y :: %d need :: %d\n",inp[i].x,need[inp[i].x],inp[i].y,need[inp[i].y]);
  257.            // ans.insert(inp[i].x); // 2i khanei bosathe hobe tai
  258.            // ans.insert(inp[i].y);
  259.           }
  260.           if(!ok) break;
  261.       }
  262.         if(!ok)
  263.       {
  264.           puts("impossible");
  265.           continue;
  266.       }
  267.       int add = 0 ;
  268.       int i ;
  269.     //  printf("hre");
  270.       for ( i =  1 ; i <= idx && ok ; i++ )
  271.       {
  272.           if(col[i]==-1)
  273.           {
  274.               C[1] = C[0] = 0 ;
  275.               ok = dfs(i,1);
  276.               add += min(C[1],C[0]);
  277.           }
  278.  
  279.       }
  280.         if(!ok)
  281.       {
  282.           puts("impossible");
  283.           continue;
  284.       }
  285.       cout << ans.size() + add << endl ;
  286.  
  287.  
  288.  
  289.  
  290.     }
  291.  
  292.  
  293.  
  294.     return 0;
  295. }
Success #stdin #stdout 0.02s 65792KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/0aQBDF
language:
C++ (gcc 8.3)
created:
10 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!