Marathon on tree , Help required, Graph problem 9 [solved]

help
, , , ,
1

Question : “MOAT Problem - CodeChef”

My solution : “CodeChef: Practical coding for everyone”

Check whether a node “r” is in the path from vertex “u” to “v”

@galencolin @everule1 @aneee004

2

Are you asking why it’s TLE, or how to optimize it?

3

How is this possible I saw two solutions -

1st -

If there is node “r” exist from path “x” to “y” then

distance from x to y >= distance from x to r + distance from r to y

while(q--){
		scanf("%d%d%d",&x,&y,&r);
		int dxy = h[x]+h[y]-2*h[lca(x,y)];
		int dxr = h[x]+h[r]-2*h[lca(x,r)];
		int dry = h[r]+h[y]-2*h[lca(r,y)];
		if(dxy<dxr+dry){
			printf("NO\n");
		}
		else{
			printf("YES\n");
		}
	}

2nd -

while(q--)
        {
            cin>>st>>end>>val;
            st--;
            end--;
            val--;
            ll vall = LCA(st,end);
            if((LCA(val,st) == val || LCA(val,end) == val) && LCA(vall,val) == vall)
            {
                cout<<"YES\n";
            }
            else
            {
                cout<<"NO\n";
            }
        }

@galencolin how this is true ?

4

No need to reply , Thanks I did :slight_smile:

5 
while(q--)
    {
        lli x,y,r;
        
        cin>>x>>y>>r;
        
        // If there is node “r” exist from path “x” to “y” then

        // distance from x to y == distance from x to r + distance from r to y
        
        lli dist_x_to_y = getDistance(x,y);
        
        lli dist_x_to_r = getDistance(x,r);
        
        lli dist_r_to_y = getDistance(r,y);
        
        if(dist_x_to_y == (dist_x_to_r + dist_r_to_y))
            print("YES");
        else
            print("NO");
    }
6

  1. visualize the path from x to y, and overlay the paths from r to x and r to y. If r is not on on the path from x to y, then at least one vertex that isn’t r will be visited by both of r's paths to x and y, and thus some distance will be “wasted”. But if r is on the path, then that won’t be true and the total distance will be exactly d(x, y).

  2. this just checks if lca(x, y) is a parent of r and r is a parent of either x or y

1 Like