MAieshAdnan's blog

Why my submission doesn't work?
By MAieshAdnan, history, 10 hours ago, In English

Hi, CodeForces!

I was solving problem 580C — Kefa and Park where I came up with this code: 300260289. However, it fails on test case 8. If I give it the input:

2 1

1 1

1 2

It outputs 0 but when I provide it "2 1" on the last input it would output 1. Why is that happening?

Any help will be deeply appreciated.

EDIT 1: I solved the problem, the error was I was reading the graph (tree) as directed and I hard coded '0' as the root so whenever '0' is not root it bugs!.

  • Vote: I like it
  • +7
  • Vote: I do not like it

»
9 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

The issue arises because your code treats the graph as a directed graph. Specifically, when constructing edges with the following line:

adj[a].push_back(b);

In this case, the input pair $$$(1$$$ $$$2)$$$ is treated differently from $$$(2$$$ $$$1)$$$. However, the problem specifies an undirected graph, meaning both pairs should be treated equivalently. To fix this, you need to construct the graph as undirected by adding edges in both directions:

adj[a].push_back(b);
adj[b].push_back(a);

This ensures that both pairs are handled correctly, maintaining symmetry in the adjacency list.

Additionally, don't forget to adjust the base case in your (DFS) function. For an undirected graph, a leaf node will have exactly one edge (to its parent), not zero.

→ Reply
  • »
    »
    8 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Aha, thank you for pointing that out.

    → Reply
»
8 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by MAieshAdnan (previous revision, new revision, compare).

→ Reply