Wrong answer in PERCAPTA

why my code is giving wrong answer in this question…

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
#define inf 1e9
#define MOD 1000000007
#define deb(x) cout<<#x<<" "<<x<<endl;
int gcd(int a, int b);
void print(int arr[], int n);
void printv(vector<int>arr);

int dfs(vector<int>v[], vector<int>&vis, int node, int mode)
{
    int cnt = 0;
    stack<int>st;
    st.push(node);
    while(st.size())
    {
        int ff = st.top();
        st.pop();
        if(!vis[ff]){
        vis[ff] = 1;
        if(mode)printf("%lld ", ff);}//cout<<ff<<" ";}
        cnt++;
        for(int x: v[ff])if(!vis[x])st.push(x);
    }
    return cnt;
}

signed main()
{
    int t;cin>>t;
    while(t--)
    {
        int n;cin>>n;
        int m;cin>>m;
        double p[n+1], in[n+1];
        for(int i=1;i<=n;i++){
            //cin>>in[i];
            scanf("%lld", &in[i]);
        }
        for(int i=1;i<=n;i++){scanf("%lld", &p[i]);}//cin>>p[i];}

        double maxi = -1;

        for(int i=1;i<=n;i++)maxi = max(maxi, in[i]/p[i]);

        vector<int>v[n+1];

        for(int i=0;i<m;i++){
            int a, b;
            scanf("%lld %lld", &a, &b);
            //cin>>a>>b;
            double aa = in[a]/p[a];
            double bb = in[b]/p[b];
            if(aa == bb && aa == maxi){
                v[a].pb(b);
                v[b].pb(a);
                //cout<<a<<" "<<b<<" "<<endl;
            }
        }

        //deb(maxi);

        vector<int>vis(n+1,0);

        pair<int, int>ans;
        ans.first = -1;
        ans.second = -1;

        for(int i=1;i<=n;i++)
        {
            if(vis[i])continue;
            int conn = dfs(v, vis, i, 0);
            if(conn > ans.second){
                ans.second = conn;
                ans.first = i;
            }
        }


        for(int i=0;i<=n;i++)vis[i]=0;

        cout<<ans.second<<endl;
        int aaa = dfs(v, vis, ans.first, 1);
        cout<<endl;
    }
}

Using floating point arithmetic will lead to precision loss. Use integers for comparison like this.

1 Like

Thanks for reply…
I have tried to change some code but still it gives WA…


#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
#define inf 1e9
#define MOD 1000000007
#define deb(x) cout<<#x<<" "<<x<<endl;
int gcd(int a, int b);
void print(int arr[], int n);
void printv(vector<int>arr);

int in[200005], p[200005];

int dfs(vector<int>v[], vector<int>&vis, int node)
{
    int cnt = 0;
    stack<int>st;
    st.push(node);
    while(st.size())
    {
        int ff = st.top();
        st.pop();
        if(!vis[ff]){
        vis[ff] = 1;}
        //if(mode)printf("%lld ", ff);}//cout<<ff<<" ";}
        cnt++;
        for(int x: v[ff])if(!vis[x])st.push(x);
    }
    return cnt;
}

void dfs2(vector<int>v[], vector<int>&vis, int node)
{
    vector<int>ans;
    stack<int>st;
    st.push(node);
    while(st.size())
    {
        int ff = st.top();
        st.pop();
        if(!vis[ff]){
        vis[ff] = 1;ans.pb(ff);}
        //if(mode)printf("%lld ", ff);}//cout<<ff<<" ";}
        //cnt++;
        for(int x: v[ff])if(!vis[x])st.push(x);
    }
    sort(ans.begin(), ans.end());
    printv(ans);
}

signed main()
{
    int t;cin>>t;
    while(t--)
    {
        int n;cin>>n;
        int m;cin>>m;
        int p[n+1], in[n+1];
        for(int i=1;i<=n;i++){
            //cin>>in[i];
            scanf("%lld", &in[i]);
        }
        for(int i=1;i<=n;i++){scanf("%lld", &p[i]);}//cin>>p[i];}

        int num = in[1], dem = p[1];

        for(int i=2;i<=n;i++){
            if(p[i] * num >= in[i]*dem)continue;
            num = in[i];
            dem = p[i];
        }

        //deb(num);deb(dem);

        int check[n+1];
        memset(check, 0, sizeof(check));

        for(int i=1;i<=n;i++)
        {
            if(p[i]*num == in[i]*dem)check[i]=1;
        }

       // print(check, n+1);

        vector<int>v[n+1];

        for(int i=0;i<m;i++){
            int a, b;
            scanf("%lld %lld", &a, &b);
            if(check[a] && check[b]){
                v[a].pb(b);
                v[b].pb(a);
                //cout<<a<<" "<<b<<" "<<endl;
            }
        }

        //deb(maxi);

        vector<int>vis(n+1,0);

        pair<int, int>ans;
        ans.first = -1;
        ans.second = -1;

        for(int i=1;i<=n;i++)
        {
            if(vis[i])continue;
            int conn = dfs(v, vis, i);
            if(conn > ans.second){
                ans.second = conn;
                ans.first = i;
            }
        }


        for(int i=0;i<=n;i++)vis[i]=0;

        cout<<ans.second<<endl;
        dfs2(v, vis, ans.first);
        //cout<<endl;
    }
}




















int gcd(int a, int b)
{
    if (b == 0)
        return a;
    return gcd(b, a % b);
}

void print(int arr[], int n)
{
    //cout<<endl<<"the array is"<<endl;
    for(int i=0;i<n;i++)cout<<arr[i]<<" ";
    cout<<endl;

}

void printv(vector<int>arr)
{
    //cout<<endl<<"the vector is"<<endl;
    for(int i=0;i<arr.size();i++)cout<<arr[i]<<" ";
    cout<<endl;
}

check out my solution if it helps. I think its readable.
Cheers.

1 Like