Magikarp's blog

By Magikarp, 10 years ago, In English

Hi I am getting TLE in the 7th test case. How do I optimize my code? Problem link: http://www.spoj.com/problems/MATCHING/

#include<cstdio>
    #include<algorithm>
    #include<iostream>
    #include<vector>
    #include<set>
    #include<cstring>

    using namespace std;

    #define in(a) scanf("%d",&a);
    #define pb push_back

    vector <int> G[50000+5];
    bool seen[50000+5];
    int matchL[50000+5],matchR[50000+5],A[50000+5];
    int n,m;

    bool bpm(int u)
    {
        for(int i=0;i<G[u].size();i++)
        {
            int v=G[u][i];
            if(seen[v])
                continue;
            seen[v]=true;

            if(matchR[v]<0 || bpm( matchR[v] ))
            {
                matchR[v]=u;
                matchL[u]=v;
                return true;
            }


        }
        return false;
    }

    int main()
    {
        int n,m,p;
        set<int> row;
        set<int> col;
        set<int>::iterator it;

        int pos=0;
        in(n);in(m);in(p);
        while(p--)
        {
            int x,y;
            in(x);in(y);
            if(row.find(x)==row.end()){
                row.insert(x);
                A[pos++]=x;
            }


            G[x].pb(y);
        }

        /*for(int i=0;i<10;i++)
            cout<<A[i]<<" ";
        cout<<endl;*/

        memset(matchL,-1,sizeof(matchL));
        memset(matchR,-1,sizeof(matchR));


        m=row.size();
        //n=B.size();
        int cnt=0;

        for(int i=0;i<m;i++)
        {
            memset(seen,0,sizeof(seen));

                if( bpm( A[i] ) )
                    cnt++;

        }
        printf("%d\n",cnt);

        return 0;
    }
  • Vote: I like it
  • +2
  • Vote: I do not like it

| Write comment?
»
10 years ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

It's obiviously that your solution can get TLE. The command "memset(seen,0,sizeof(seen))" is called exactly m times (m<=50000). It's impossible to memset an array of size 50000 for 50000 times in 3s.

You should also notice that, this problem can't be solved by regular max-matching algorithm. You must use Hoftcroft-Karp or Dinitz to solve it.