Problem A:
Check whether exist a pair i and j,they satisfy xi+di = xj && xj+dj = xi;
Problem B:
Pay attention to Just Right or Red. use Div and Mod can solve it easily;
Problem C:
As we know, there are only two path -- forward and reverse, so we can do DFS from the one-degree nodes (only two nodes).
As their index may be very larger, so I used map<int,int> to do hash.
void dfs(int i)
{
int sz = mat[i].size()-1, j;
UF(j,0,sz)
if (!vis[mat[i][j]])
{
vis[mat[i][j]] = 1;
printf(" %d",val[mat[i][j]]);
dfs(mat[i][j]);
}
}
Problem D:
Floyd.
First, Floyd pretreat the path from I to J, and save the path.
Then get the answer.
The order is a1,a2...ak, K is the number of the leaves, we can assume a0 = ak+1 = 1, the root.
then, answer push_back the path[ai][ai+1].
if the ans.size() > 2*N-1 , cout -1;
else cout the answer.
Check whether exist a pair i and j,they satisfy xi+di = xj && xj+dj = xi;
Problem B:
Pay attention to Just Right or Red. use Div and Mod can solve it easily;
Problem C:
As we know, there are only two path -- forward and reverse, so we can do DFS from the one-degree nodes (only two nodes).
As their index may be very larger, so I used map<int,int> to do hash.
void dfs(int i)
{
int sz = mat[i].size()-1, j;
UF(j,0,sz)
if (!vis[mat[i][j]])
{
vis[mat[i][j]] = 1;
printf(" %d",val[mat[i][j]]);
dfs(mat[i][j]);
}
}
Problem D:
Floyd.
First, Floyd pretreat the path from I to J, and save the path.
Then get the answer.
The order is a1,a2...ak, K is the number of the leaves, we can assume a0 = ak+1 = 1, the root.
then, answer push_back the path[ai][ai+1].
if the ans.size() > 2*N-1 , cout -1;
else cout the answer.
path[i][j], from i to j;
then, just push all the path, from 1 to next leaf, and come back 1.
full solution using lca, better complexity
Same complexity without LCA. For each leaf y let leaf_pos[y] be the position of the leaf in the desired visit order. For each node x let dp[x] be min value of any leaf_pos for all leaves rooted in the subtree of x. Then do a dfs visiting nodes in order of increasing value of dp. 92775116
wow, thats smart, very clean code. i think its important to solve problems, using different approaches. learned something new, thanks
if (sum != 2 * n — 2) { fine = 0; }
what is the meaning of this line in your code?plz explain
there are n — 1 edges in a tree, in the problem you are asked to find path from root to root such that you go through each edge only two times, thus total walked distance is 2 * (n — 1) = 2 * n — 2.
Thanks a lot,sir!
About problem D.
Since the route between two nodes in a tree can be split into two parts by their least common ancestor, I think maybe a better solution would using directly walk between two adjacent nodes by passing their lca and connect the edges.
Although, since n is small enough, Floyd is just good for it. :-)
can anyone post the idea for 29E
It's a shortest path problem. The state is u, v, t, which means person 0 is at vertex u, person 1 is at vertex v, and person t must move now. For t = 1, you have to check that the vertex you move to is different from u. You can solve it with BFS.
Thank you very much
Thanks. That was really helpful.
why should we use map ?
Assuming the question is for C, the range of numbers is from 1 to 10^9 which means to store graph you will use an array of size 10^9 which is beyond the memory limit of your hardware.
fuckoff @onlyone is this editorial or a Treasure hunting letter??.
For problem C, it's simply finding the diameter of a tree. You can use two DFSs to do so.