zeyad.alaaeldin2016's blog

ecpc problem H Find the path
By zeyad.alaaeldin2016, history, 4 years ago, In English

https://codeforces.net/gym/101992/problem/H

I was solving this problem by BFS from start node and checking what is the max edge while moving to level K.

https://ideone.com/IcEBeh

I dont know why codeforces sample gives me a lot of zero. while on my codeblocks give me 104 and 7 ... anyone know where is the problem ?

  • Vote: I like it
  • -4
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it +5 Vote: I do not like it

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

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +6 Vote: I do not like it

You haven't read the input from a file. You can easily solve that by adding freopen right after your main function(inside the main function):

freopen("path.in","r",stdin);

If you are participating in this year's ECPC, you should already know that you take the input usually from a file.

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

    sorry didnt notice that i have to do it .. now it gives me wrong answer.. any idea what is wrong ?

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

      You don't use value l anywhere? You might have misunderstood the problem I think.

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        yes, I misunderstood it, so let me recap what I understood.

        i need to find a path of L edges and sort the weight of the path so i can get the largest edge on Kth position, isnt it ?

        if so, i am stuck in how i am going to know that this is the perfect path that gives me largest edge on kth position

        → Reply
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
          ← Rev. 4   Vote: I like it 0 Vote: I do not like it

          Edit: Nevermind I misunderstood the problem(I thought we can only move through simple paths) so I over-complicated the solution. Because you can move through the same edge multiple times, then for the edge to be the Kth, you must have covered that edge before or equal when you reached the Kth vertex. So the problem became simpler:

          Given N and K, find the largest weighted edge that exists when visiting all paths from u(initial) by visiting at most K vertices other than the initial node. Because when you find that edge, you can just keep re-crossing it again and again and again till we reach L(our target length).

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

            actually i was doing that i think.. i used bfs to know the level by that i can know how many vertices i visit from the u (initial) and then i get the max weight when level <= k, is that what you talking about ?

            and can you get accepted in it to make sure both of us understand the problem well ?

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

              It turns out that your $$$lev$$$ array you don't clear it well after each testcase.

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

                amm how ? i for loop on them and put it equal 0. and i put memset to make sure if i miss something. but i still get wrong

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

                  In an old submission, it was wrong. I guess you fixed it. Anyways, here is the bug in your last code:

                  for(auto v : adj[u])
            {
                if(lev[v.first]<=k)
                    mx=max(v.second,mx);
                if(!lev[v.first])
                    q.emplace(v.first), lev[v.first] = lev[u] + 1;
            }

                  you should swap the two ifs and it will get accepted. The reason for that is that you check if $$$level<=k$$$ although sometimes it is 0 as it is not set yet.

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

                  Finally !!! . this is a dumb bug actually xD i appreciate that you helped me !

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

    BTW in line 45 should be lev[i] but i forgot to update it on ideone

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

      Its okay. I have coach mode on so I can see all your gym submissions.

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

        if(lev[v.first]<=k) here level starting from 1. for level 2 , there with be 1 weight. they ask for kth weight . why not if(lev[v.first]<=k+1)? got confused.

        → Reply