Fine Art Solution | Canada Day Contest 2021

Fine Art Solution

Deruikong is a highly skilled artist. He wants to build a scuplture out of wool in Minecraft. He has nn types of wool, the iith of which is of color (xi,yi,zi) xi,yi,zi) (xi%xi% red, yi%yi% green, zi%zi% blue using the RGB color model).

See Also : Canada Day Contest 2021

His build contains qq pixels, the iith of which is of color (Xi,Yi,Zi)(Xi,Yi,Zi). Help Deruikong choose a good substitute for each pixel ii by finding the wool jj that minimizes |Xi−xj|+|Yi−yj|+|Zi−zj||Xi−xj|+|Yi−yj|+|Zi−zj|. If there are multiple solutions, output the smallest value of jj.

Constraints

1≤n,q≤1500001≤n,q≤150000

0≤xi,yi,zi,Xi,Yi,Zi≤1000≤xi,yi,zi,Xi,Yi,Zi≤100

No two wool types have the same color.

Input Specification

The first line will contain two space-separated integers, nn and qq.

The next nn lines contain three space-separated integers, xixi, yiyi, and zizi for 1≤i≤n1≤i≤n.

The next qq lines contain three space-separated integers, XiXi, YiYi, and ZiZi for 1≤i≤q1≤i≤q.

Output Specification

For each pixel, output the lowest index of the closest substitute.

Sample Input 1

2 3
0 0 0
0 0 5
0 0 0
0 0 3
0 0 4

Sample Output 1

1
2
2

Sample Input 2

2 3
3 3 3
1 1 1
2 2 2
1 2 3
3 2 1

Sample Output 2

1
1
1

Hint

There are only 1003=10000001003=1000000 possible colors.

Hint

Try converting the grid into a graph.

Solution

Perform a multisource breadth first search from each of the paints to find the closest paint for every possible color. Now the answer to each query has been calculated.

Complexity: O(max(xi,yi,zi,Xi,Yi,Zi)3+q)

Leave a Comment

Please Click on 1 or 2 Ads to help us run this site.
+