Mine and Tree

View as PDF

Submit solution

All submissions

Best submissions

Points: 30 (partial)

Time limit: 2.5s

Memory limit: 256M

Author:

FatalEagle

Problem types

In her spare time, Mine enjoys game shows and mathematics. In particular, she really likes geometry and graph theory. Today, she is a participant on the popular game show GeomeTree, where contestants show off their mathematical skills by performing operations on a point in the 2D coordinate plane, all while on a tree. Mine is in it to win it!

Each contestant is given an undirected graph with $N$ ~N~ $(1 \le N \le 10^5)$ ~(1 \le N \le 10^5)~ vertices and $N-1$ ~N-1~ edges such that there is a unique path between every pair of vertices — a tree. On each vertex of the tree, an operation is written on it. The operation may either be "rotate your point by $\theta$ ~\theta~ $(0 \le \theta < 360)$ ~(0 \le \theta < 360)~ degrees counterclockwise around the origin", "translate your point by a vector $(dx, dy)$ ~(dx, dy)~ $(-10^5 \le dx, dy \le 10^5)$ ~(-10^5 \le dx, dy \le 10^5)~", or "move the point towards (but not past) another point $(p, q)$ ~(p, q)~ $(-10^5 \le p, q \le 10^5)$ ~(-10^5 \le p, q \le 10^5)~ such that the new distance between these points is $P\%$ ~P\%~ $(0 \le P < 100)$ ~(0 \le P < 100)~ of the old distance". Contestants perform $M$ ~M~ $(1 \le M \le 10^5)$ ~(1 \le M \le 10^5)~ rounds of queries on this tree. Each round, there are two possible queries the contestant needs to perform.

The first kind of query is when the contestant is given two vertices of the tree $(u, v)$ ~(u, v)~ $(1 \le u, v \le N)$ ~(1 \le u, v \le N)~ and a point $(x, y)$ ~(x, y)~ $(-10^5 \le x, y \le 10^5)$ ~(-10^5 \le x, y \le 10^5)~. The contestant has to move the point from vertex $u$ ~u~ of the tree to vertex $v$ ~v~ of the tree, performing every operation written on the vertices to the point they were given along the way (including the operations on vertices $u$ ~u~ and $v$ ~v~). Operations are cumulative, and you have to perform the operations sequentially.

The second kind of query is when the operation on a tree changes. The new operation will still be either a rotation, translation, or moving operation in accordance with the constraints above.

The first place prize in the game show is unlimited riches along with a platinum pass to a love hotel for two. We know which prize Mine is really interested in. However, all the other contestants are writing programs to play this ridiculously difficult game show for them. Since Mine is in a huge pinch right now, she has hired you to help her win! You have no choice but to write a program that helps her, otherwise you will be blasted into pieces by Pumpkin!

Input Specification

All the numbers in the input are integers.

The first line of input will have $N$ ~N~ and $M$ ~M~, separated by a single space.

The next $N$ ~N~ lines will each have the operation of each vertex of the tree, in order from $1 \dots N$ ~1 \dots N~.

An operation is one of the following:

R θ is the rotate by $\theta$ ~\theta~ degrees operation.
T dx dy is the translate by $(dx, dy)$ ~(dx, dy)~ operation.
M p q P is the move towards $(p, q)$ ~(p, q)~ such that the new distance is $P\%$ ~P\%~ of the original distance operation.

The next $N-1$ ~N-1~ lines describe the graph. Each line is a pair of vertices which are connected by an edge in the graph. There will be no self-loops or duplicate edges, and it is guaranteed that the resulting graph is a tree.

The next $M$ ~M~ lines will describe the queries.

If the line begins with:

Q it will be followed by u v x y, indicating the first kind of query.
U it will be followed by u and the new operation on vertex $u$ ~u~, in the same format as above, indicating the second kind of query.

Output Specification

For each Q query, output two space-separated real numbers, the final coordinates of the input point. Both of these numbers should be within an absolute or relative error of at most $10^{-6}$ ~10^{-6}~.

Tips

Some of the test cases will have $N$ ~N~ and/or $M$ ~M~ very small. Some of the test cases will only have one or two types of operations. This information may be helpful if you're aiming for partial marks. For example, a well-implemented $\mathcal{O}(NM)$ ~\mathcal{O}(NM)~ solution in a fast language might get up to 55% of the marks for this problem.

Sample Input 1

1 1
M 4 4 75
Q 1 1 0 0

Sample Output 1

1.000000 1.000000

Sample Input 2

2 3
R 45
R 135
1 2
Q 1 1 100 100
Q 1 2 100 100
Q 2 2 100 100

Sample Output 2

0.000000 141.421356
-100.000000 -100.000000
-141.421356 0.000000

Sample Input 3

5 8
R 90
T 1 1
R 45
T 3 2
R 0
1 2
2 3
3 4
4 5
Q 1 1 0 0
Q 3 3 -4 9
U 5 R 180
Q 1 5 1 1
Q 5 1 1 1
U 2 T 3 -1
Q 2 3 3 5
Q 3 1 13 37

Sample Output 3

0.000000 0.000000
-9.192388 3.535534
-1.585786 -3.414214
-3.121320 1.707107
1.414214 7.071068
-34.355339 -13.970563

Sample Input 4

20 10
M 17799 86094 84
T 30788 -16797
M 52445 -47508 4
T 26532 51287
T -50591 96517
M 30308 -85463 63
T -12715 53304
R 98
R 175
M -87887 80937 50
T 97336 -1201
R 341
R 138
M 5953 -7108 94
M 54046 65569 12
M 73656 25913 73
M 77721 -53360 30
R 212
T 68308 -46135
R 168
20 18
5 18
1 18
11 5
8 11
12 18
19 1
16 1
10 16
13 19
17 12
3 13
7 16
14 17
2 5
9 1
15 3
4 5
6 20
Q 1 9 -94625 41969
Q 5 4 -36490 77405
Q 4 14 -22835 -22452
Q 3 12 69121 18026
Q 12 3 96668 -18244
U 12 R 167
Q 3 4 -36148 25858
U 14 M -50430 -4710 38
Q 1 19 -14698 -71595
Q 9 3 77136 -81565

Sample Output 4

72072.373558 -55521.798455
-60549.000000 225209.000000
72334.627176 -67005.847616
-43561.121525 -43816.554934
51641.774285 -44852.076359
-54419.181070 93065.877003
58809.520000 -92499.760000
48861.404178 -46505.826597

Comments

1

jeffreyl commented on Dec. 28, 2014, 11:22 p.m.

Can I see which signal I'm runtime erring with?

1

FatalEagle commented on Dec. 28, 2014, 11:25 p.m.

SIGSEGV. Your array sizes are too small for the constraints. $10^5 = 100\,000$ ~10^5 = 100\,000~

1

jeffreyl commented on Dec. 29, 2014, 12:59 a.m.

Thanks, don't know how I missed that

0

FatalEagle commented on Dec. 25, 2014, 7:32 p.m.

The input specification did not mention the edges in the tree previously, but that has been corrected.

-11

bobhob314 commented on Dec. 25, 2014, 11:33 p.m.

Hey FatalEagle,

Can I be an admin with the red coloured name attribute? Or at least, even if you can't let me do admin-y stuff, can you just make my name red, or GREEN because it's really cool? And can I please have the ability to post private problems?

THAT WOULD BE AWESOME.

JUST LIKE YOU ARE AWESOME.

I love you FatalKawaii (8^* ) /Javazoned again/. Hopefully you receive these messages well.

hob

This comment is hidden due to too much negative feedback. Show it anyway.

21

quantum commented on Dec. 25, 2014, 11:47 p.m.

I am sorry, but we don't offer red colours to anyone but admins. However, if you don't like your colour, we do offer the option of not showing your name at all – it's called banning.

1

100cottage commented on Dec. 26, 2014, 1:58 a.m.

I was just curious, how do they coloured names work? I know that Red is Admin, but what do purple or the other colours mean?

2

FatalEagle commented on Dec. 26, 2014, 2:06 a.m.

Red - Admin

Purple - Problem Setter (author of at least 1 problem on DMOJ, and/or plans to set problems in the future on DMOJ)

Blue - Normal user

0

100cottage commented on Dec. 26, 2014, 2:12 a.m.

How would we go through the process of submitting a problem?

1

FatalEagle commented on Dec. 26, 2014, 2:15 a.m.

Email us at dmcioj -at- gmail.com or contact an admin personally if you somehow get our contact info (no, I won't give it to you right now). We'll see if your problem isn't too easy, impossible to solve, a copy of an existing problem, etc. If we like the problem, we'll make you a problemsetter and we can proceed from there.

-1

bobhob314 commented on Dec. 26, 2014, 1:24 a.m.

:( I'm sorry if I offended anyone. I don't know if that was a joke or a threat so I won't make a joke out of this comment.

So how would one go about becoming an admin? Is being in the DMCI a requirement?

-hob

4

omaewamoushindeiru commented on Dec. 26, 2014, 4:05 a.m.

hob sits down

0

FatalEagle commented on Dec. 26, 2014, 2:06 a.m.

The red color is reserved for developers of the site/judge. Since quantum has put a lot of time into this project, I expect that he has very strong opinions on this issue. Don't take the comment personally, we do not ban without good reason.

As for "being in DMCI" a requirement, I don't think it is, but it's unlikely that we'll have more admins for DMOJ.