daihan's blog

764C — Timofey and a tree Getting TLE
By daihan, 8 years ago, In English

Hello codeforces community , i am getting TLE . My logic is : First i store those edges node to set those which color are different , then i put a simple dfs on each of the node stored in set which will be exact for root i break the loop and print it . If i aint found a node , print no . Now I understand for which case i got TLE . If i can stop calling dfs again and again , i can reduce TLE . But can find the logic .

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

Comments Comments (5)
| Write comment?
»
8 years ago, # |
  Vote: I like it -18 Vote: I do not like it

think stupid

→ Reply
»
8 years ago, # |
  Vote: I like it +1 Vote: I do not like it

first of all, you need a vis array for your dfs function

second, you don't have to check all the edges with different colors, it's enough to check only the nodes of one of this edges, then you get the result.

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    You don't need a visited array, because it's a tree, just enough to check a parent.

    second, 

            set<int > point;
        fr(i,0,n-2)
        if(c[ed[i].first ] != c[ed[i].second ])
        {
            point.insert(ed[i].first);
            point.insert(ed[i].second);

             break; //--->see, enough a single edge , and you will GOT AC ! 
        }
    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yes you are right, I didn't notice that his code deals with the parent...

      → Reply