monyet's blog

By monyet, 10 years ago, In English

Hello, i'm trying to solve this problem http://www.spoj.com/problems/PT07X/. I wrote a brute force algorithm. I was expecting a Time Limit Exceeded response, but I got WA instead. What is wrong with my code? Thanks!

vector<pair<int,int> > edge;
     int n , a , b ,mini;
     
     scanf("%d",&n);
     for (int i = 1; i<=n-1; i++)
     {
         scanf("%d%d",&a,&b);
         a--; b--;
         edge.push_back(make_pair(a,b));
     }
     
     mini = INF;
     for (int mask = 0; mask < (1<<n); mask++)
     {
         bool can = true;
         for (int i = 0 ; i<edge.size(); i++)
         {
             if ( (mask&(1<<edge[i].first))==0 && (mask&(1<<edge[i].second))==0) 
             {
                  can = false;
                  break;
             }
         }
         
         if (can)
         {
             int on = 0;
             for (int i = 0 ; i<n; i++) if ( (mask&(1<<i))!= 0) on++;
             mini = min(mini,on);
         }
     }
     
     printf("%d\n",mini);
  • Vote: I like it
  • -3
  • Vote: I do not like it

»
10 years ago, # |
Rev. 2   Vote: I like it +6 Vote: I do not like it

for (int mask = 0; mask < (1<<n); mask++)

N<=100000

What do you expect?