Why this code giving WA

#1

#include<bits/stdc++.h>
using namespace std;

#define nL “\n”
#define pii pair<int, int>

class Graph {
int V;
list *l;

public:
Graph(int v)
{
V = v;
l = new list[V];
}

void addEdge(int u, int v, int cost)
{
	l[u].pb({v, cost});
	l[v].pb({u, cost});
}

int DFS(int u, bool *vis, int *count, int &ans)
{
	vis[u] = true;
	count[u] = 1;

	for (auto nbr : l[u])
	{
		int v = nbr.first;
		int wt = nbr.second;

		if (!vis[v])
		{
			count[u] += DFS(v, vis, count, ans);

			int nx = count[v];
			int ny = V - nx;

			ans += 2 * min(nx, ny) * wt;
		}
	}
	return count[u];
}

int maxDist()
{
	bool *vis = new bool[V];
	int *count = new int[V];

	for (int i = 0; i < V; i++)
	{
		vis[i] = false;
		count[i] = 0;
	}

	int ans = 0;
	DFS(0, vis, count, ans);

	return ans;
}

};

int32_t main()
{
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);

#ifndef ONLINE_JUDGE
freopen(“input.txt”, “r”, stdin);
freopen(“output.txt”, “w”, stdout);
#endif

int t;
cin >> t;

while (t--)
{
	int n;
	cin >> n;

	Graph g(n);

	for (int i = 0; i < n - 1; i++)
	{
		int x, y, z;
		cin >> x >> y >> z;

		g.addEdge(x, y, z);
	}

	cout << g.maxDist();

}

return 0;

}

#2

Hello @devang_11912089,

There are a few errors,

  1. While inputting edges (x,y) it’s in one based indexing while everything in your code is 0 based.
  2. You should use long int for ans as the final answer can be greater than 1e9.
  3. pb is undefined you should first define pb as push_back
#4

can you point out mistakes in code

#include<bits/stdc++.h>

using namespace std;

#define ll long long

#define li long int

#define ull unsigned long long

#define lli long long int

#define nL “\n”

#define pb push_back

#define mk make_pair

#define pii pair<int, int>

#define a first

#define b second

#define vi vector

#define all(x) (x).begin(), (x).end()

#define umap unordered_map

#define uset unordered_set

#define f(i, n) for(i=0; i<n; i++)

#define F(i, k, n) for(i=k; i<n; i++)

#define imax INT_MAX

#define imin INT_MIN

#define exp 1e9

#define sz(x) (int((x).size()))

#define MOD 1000000007

class Graph {

int V;

list<pii> *l;

public:

Graph(li v)

{

    V = v;

    l = new list<pii>[V];

}

void addEdge(li u, li v, li cost)

{

    l[u].pb({v, cost});

    l[v].pb({u, cost});

}

int DFS(li u, bool *vis, li *count, li &ans)

{

    vis[u] = true;

    count[u] = 1;

    for (auto nbr : l[u])

    {

        li v = nbr.first;

        li wt = nbr.second;

        if (!vis[v])

        {

            count[u] += DFS(v, vis, count, ans);

            li nx = count[v];

            li ny = V - nx;

            ans += 2 * min(nx, ny) * wt;

        }

    }

    return count[u];

}

int maxDist()

{

    bool *vis = new bool[V];

    li *count = new li[V];

    for (li i = 0; i < V; i++)

    {

        vis[i] = false;

        count[i] = 0;

    }

    li ans = 0;

    DFS(0, vis, count, ans);

    return ans;

}

};

int32_t main()

{

ios_base::sync_with_stdio(0);

cin.tie(0); cout.tie(0);

/*Graph g(4);

g.addEdge(0, 1, 3);

g. addEdge(1, 2, 2);

g.addEdge(2, 3, 2);

cout << g.maxDist() << endl;

*/

int t;

cin >> t;

while (t--)

{

    li n;

    cin >> n;

    Graph g(n);

    for (li i = 1; i <= n - 1; i++)

    {

        li x, y, z;

        cin >> x >> y >> z;

        g.addEdge(x, y, z);

    }

    cout << g.maxDist();

}

return 0;

}

#5

@devang_11912089,

This is the link to the problem, right?

#6

Yes this is the link to problem

#7

@devang_11912089,

Code:

#include<bits/stdc++.h>

using namespace std;

#define ll long long

#define li long int

#define ull unsigned long long

#define lli long long int

#define nL “\n”

#define pb push_back

#define mk make_pair

#define pii pair<int, int>

#define a first

#define b second

#define vi vector

#define all(x) (x).begin(), (x).end()

#define umap unordered_map

#define uset unordered_set

#define f(i, n) for(i=0; i<n; i++)

#define F(i, k, n) for(i=k; i<n; i++)

#define imax INT_MAX

#define imin INT_MIN

#define exp 1e9

#define sz(x) (int((x).size()))

#define MOD 1000000007

ll ans;

class Graph {

    int V;

    list<pii> *l;

public:

    Graph(li v)

    {

        V = v;

        l = new list<pii>[V];

    }

    void addEdge(li u, li v, li cost)

    {

        l[u].pb({v, cost});

        l[v].pb({u, cost});

    }

    li DFS(li u, bool *vis, li *count)

    {

        vis[u] = true;

        count[u] = 1;

        for (auto nbr : l[u])

        {

            li v = nbr.first;

            li wt = nbr.second;

            if (!vis[v])

            {

                count[u] += DFS(v, vis, count);

                li nx = count[v];

                li ny = V - nx;

                ans += 2 * min(nx, ny) * wt;

            }

        }

        return count[u];

    }

    li maxDist()

    {

        bool *vis = new bool[V+1];

        li *count = new li[V+1];

        for (li i = 0; i < V; i++)

        {

            vis[i] = false;

            count[i] = 0;

        }

        ans = 0;

        DFS(0, vis, count);

        return ans;

    }

};

int32_t main()

{

    ios_base::sync_with_stdio(0);

    cin.tie(0); cout.tie(0);

    int t;

    cin >> t;

    for(int j = 1;j<=t; j++)

    {

        li n;

        cin >> n;

        Graph g(n);

        for (li i = 1; i <= n - 1; i++)

        {

            li x, y, z;

            cin >> x >> y >> z;

            g.addEdge(x-1, y-1, z); //0-based indexing

        }      

        //change cout statements accounding to question

        cout << "Case #" << j << ": " << g.maxDist() << endl;

    }

    return 0;

}
#8

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.