TopCoder

User's AC Ratio

100.0% (2/2)

Submission's AC Ratio

100.0% (2/2)

Tags

Description

http://icpc.iisf.or.jp/past-icpc/regional2017/problems.pdf
Alyssa is a college student, living in New Tsukuba City. All the streets in the city are oneway.
A new social experiment starting tomorrow is on alternative traffic regulation reversing
the one-way directions of street sections. Reversals will be on one single street section between
two adjacent intersections for each day; the directions of all the other sections will not change,
and the reversal will be canceled on the next day.
Alyssa orders a piece of pizza everyday from the same pizzeria. The pizza is delivered along the
shortest route from the intersection with the pizzeria to the intersection with Alyssa’s house.
Altering the traffic regulation may change the shortest route. Please tell Alyssa how the social
experiment will affect the pizza delivery route.

Input Format

The input consists of a single test case in the following format.
n m
a1 b1 c1
.
.
.
am bm cm
The first line contains two integers, n, the number of intersections, and m, the number of street
sections in New Tsukuba City (2 ≤ n ≤ 100 000, 1 ≤ m ≤ 100 000). The intersections are numbered 1 through n and the street sections are numbered 1 through m.
The following m lines contain the information about the street sections, each with three integers ai, bi, and ci (1 ≤ ai ≤ n, 1 ≤ bi ≤ n, ai 6= bi, 1 ≤ ci ≤ 100 000). They mean that the street section numbered i connects two intersections with the one-way direction from ai to bi, which will be reversed on the i-th day. The street section has the length of ci. Note that there may be more than one street section connecting the same pair of intersections.
The pizzeria is on the intersection 1 and Alyssa’s house is on the intersection 2. It is guaranteed that at least one route exists from the pizzeria to Alyssa’s before the social experiment starts.

Output Format

The output should contain m lines. The i-th line should be
• HAPPY if the shortest route on the i-th day will become shorter,
• SOSO if the length of the shortest route on the i-th day will not change, and
• SAD if the shortest route on the i-th day will be longer or if there will be no route from the pizzeria to Alyssa’s house.
Alyssa doesn’t mind whether the delivery bike can go back to the pizzeria or not.

Sample Input

10 14
1 7 9
1 8 3
2 8 4
2 6 11
3 7 8
3 4 4
3 2 1
3 2 7
4 8 4
5 6 11
5 8 12
6 10 6
7 10 8
8 3 6

Sample Output

SOSO
SAD
HAPPY
SOSO
SOSO
SOSO
SAD
SOSO
SOSO
SOSO
SOSO
SOSO
SOSO
SAD

Hints

Problem Source

ACM-ICPC 2017 Asia Tsukuba Regional

Subtasks

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 2000 262144 65536
1 2000 262144 65536
2 2000 262144 65536
3 2000 262144 65536
4 2000 262144 65536
5 2000 262144 65536
6 2000 262144 65536
7 2000 262144 65536
8 2000 262144 65536
9 2000 262144 65536
10 2000 262144 65536
11 2000 262144 65536
12 2000 262144 65536
13 2000 262144 65536
14 2000 262144 65536
15 2000 262144 65536
16 2000 262144 65536
17 2000 262144 65536
18 2000 262144 65536
19 2000 262144 65536
20 2000 262144 65536
21 2000 262144 65536
22 2000 262144 65536
23 2000 262144 65536
24 2000 262144 65536
25 2000 262144 65536
26 2000 262144 65536
27 2000 262144 65536
28 2000 262144 65536
29 2000 262144 65536
30 2000 262144 65536
31 2000 262144 65536
32 2000 262144 65536
33 2000 262144 65536
34 2000 262144 65536
35 2000 262144 65536
36 2000 262144 65536
37 2000 262144 65536
38 2000 262144 65536
39 2000 262144 65536
40 2000 262144 65536
41 2000 262144 65536
42 2000 262144 65536
43 2000 262144 65536
44 2000 262144 65536
45 2000 262144 65536
46 2000 262144 65536