I am getting Time Limit Exceeded for that problem. If anyone can please help. Thanks in advance :)

My approach: By calling N times BFS i got all pairs shortest path. Then by recursively i took all possible 4 nodes as there is no sub-problems so only backtracking can handle this.

Problem Link: http://codeforces.com/contest/667/problem/D

My solution Link: http://codeforces.com/contest/667/submission/17699475

For find out second best spanning tree is needed to first build mst tree and for each edge from mst tree flag them then again run kruskal. But how to find second best spanning tree only using union find data structure or lca. I want to know both ways :( Thanks in advance :)

I am stuck in this problem for a particular steps. Let me describe what my approach to solve this problem.

I take two list for both ^ and _ characters position. So both list are sorted. For each value from _ list i did binary search to find out the nearest position value from ^ character list. For example if list for ^ is : 1 3 4 5. and list for _ is : 2 5 6 Output For 2 value from the _ list is: 1 and 3[using binary search] from ^ list. So for next _ characters position 1 and 3 cant be used again and i need to mark them.Here is my problem if i mark them and erase them from the ^ list i am getting TLE. Is there any efficient way to mark them and doing binary search again?

Thanks in advance.

Problem Link: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=4917