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 = a

then, answer push_back the path[ai][a

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 = a

_{k+1}= 1, the root.then, answer push_back the path[ai][a

_{i+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

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 vertexu, person 1 is at vertexv, and persontmust move now. Fort= 1, you have to check that the vertex you move to is different fromu. 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.