Getting WA in Rainbow Graph

general
1

My approach:

for n<=2 answer is always 0.

else

basically all the nodes that are having this condition getting satified->“every node in the subset has at least two edges of different colors” will atleast form a trio that means something like “ABC”.

So checking n*(n-1)*(n-2) trios I am assigning each trio a specific number and in a vector i am storing that given numbered trio contains which all nodes( basically it contains 3 nodes).I am also storing the trio number corresponding to each edge( lets say the trio is ABC and is numbered 5 so i am storing AB->5 BC->5 AC->5)

Then I am applying DSU

Now I am checking in which all trios 2 nodes are common and if 2 nodes are common I am appending its trio number to the same component.(For example if I have ABC as a trio and BCD as a trio ,I will add ABC and BCD in same component).

Finally I will insert the nodes of each trio which belong to the same component and compute the maximum size of the set.

I wrote a test generation code:


#include "bits/stdc++.h"
using namespace std;
#define ll long long int
int main()
{
    freopen("rtest.txt","w",stdout);
    ll i,j,k,t,n;
    t=35;
    cout << t<<"\n";
    while(t--)
    {
        n=rand()%30;
        n++;
        cout << n <<"\n";
        ll mat[n+1][n+1];
        ll val=(n*(n-1));
        val/=2;
        val++;
        memset(mat,0,sizeof mat);
        for(i=1;i<=n;i++)
        {
            for(j=i+1;j<=n;j++)
            {
                k=rand()%(val);
                k++;
                mat[i][j]=mat[j][i]=k;
            }
        }
        for(i=1;i<=n;i++)
        {
            for(j=1;j<=n;j++)
            {
                cout << mat[i][j] << " " ;
            }
            cout<<"\n";
        }
    }
    return 0;
}

My submission-> https://www.codechef.com/viewsolution/13132468

I have generated 6 files and tested my code for all the cases and it passes in all these cases which were checked with an AC submission.

Can someone please tell where I am going wrong? If possible provide some testcases.

2 Likes