Блог пользователя daihan

764C — Timofey and a tree Getting TLE
Автор daihan, 8 лет назад, По-английски

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 .

  • Проголосовать: нравится
  • +1
  • Проголосовать: не нравится

»
8 лет назад, # |
  Проголосовать: нравится -18 Проголосовать: не нравится

think stupid

→ Ответить
»
8 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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.

→ Ответить
  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    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 ! 
        }
    → Ответить
    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      → Ответить