10977 - Enchanted Forest

[marcadian]

i've tried the test case and my program give same result, but it gets TLE can anybody help me?? here is my code

Code: Select all

cut

[asif_rahman0]

Use your following processing while you are taking Input.

Code: Select all

for (i=1;i<=r;i++)
				for (j=1;j<=c;j++)
					for (k=0;k<n;k++)
						if (sqrt(sqr(v[k].x-i)+sqr(v[k].y-j)) <= (double)s[k] )
							map[i][j] = blocked;

And it is O(r*c*n).
For clarity:

Code: Select all

.....
cin >>n; 
      for (i=1;i<=n;i++) 
      { 
         cin >>p.x>>p.y>>l; 
         //Put here the above code
         v.push_back(p); 
         s.push_back(l); 
      } 
...............

Also you have to do something there . Hope you got it.
bye

[marcadian]

now it gets WA, could somebody give me test case?

Code: Select all

cut

[asif_rahman0]

Look at this part:

Code: Select all

......
scanf("%d",&n); 
      for (k=1;k<=n;k++) 
      { 
         scanf("%d %d %d",&p.x,&p.y,&l); 
         int lr,lc; 
         lr = p.x + l; 
         lc = p.y + l; 
         int ii = p.x-l; 
         int jj = p.y-l; 
         for (i=ii;i<=lr;i++) 
            for (j=jj;j<=lc;j++) 
            if(i>=1&&j>=1&&i<=r&&j<=c) if (( (p.x-i)*(p.x-i)+ (p.y-j)*(p.y-j) ) <= (l*l) ) 
                     map[i][j] = blocked; 
      }
.....

Just compare with yours!

[marcadian]

yeah i also think like that but i think if i move the boundary so i need not to check whether the i and j is valid will be same with ur code??

i change to this

Code: Select all

int lr,lc;
			lr = p.x + l;
			lc = p.y + l;
			int ii = p.x-l;
			int jj = p.y-l;

			for (i=ii;i<=lr;i++)
				for (j=jj;j<=lc;j++)
				if (i>0 && i<r && j>0 &&j<c) if (( (p.x-i)*(p.x-i)+ (p.y-j)*(p.y-j) ) <= (l*l) )
							map[i][j] = blocked;

but also WA

[asif_rahman0]

Hey,
You start row from 1 to r & coloumn from 1 to c.
Then why r u checking less than r & c?
Yours:

Code: Select all

if (i>0 && i<r && j>0 &&j<c) 

Mine(accepted):

Code: Select all

if(i>=1&&j>=1&&i<=r&&j<=c) 

Just only one ERROR.

Please remove your code.

[marcadian]

oh yes thank you for that and sorry for the code i've removed it, but the true mistake is I print "Impossible" it should be "Impossible." (with dot) what a silly mistake

[Shafaet_du]

I am currently ranked 1 in this problem . sample code given in this board is enough correct your code(check page 2).

[DD]

I think there is no precision issue in this problem. It is possible to directly compare two numbers. People who got W.A. should check BFS.

[outsbook]

BFS Problem with some extra work

1. For each block location(R,C), set grid[R][C]=false
2. Jigglypuff at location (R,C) having loudness L blocks all grid points (r,c) satisfying: . so, you do not need to use floating point. If (r,c) satisfy then set grid[r][c]=false.
Now you got all unsafe location.
For input
10 10
4
1 5
2 3
4 1
8 10
4
3 2 0
5 6 3
10 1 4
10 8 1
You got the grid is
0000100000
0010010000
0101111100
1001111100
0011111110
1001111100
1111111100
1111010001
1111000100
1111101110
Here 0=safe location, and 1=unsafe location.

3. Run BFS from stating location(1,1). For each location(x,y) you got 4 adjacency location (x,y-1),(x,y+1),(x-1,y),(x+1,y) , if the adjacency location is safe location then the adjacency push to queue.
4. If you can reach to final location then print length of shortest path.
5. If you can not reach to final location then print "Impossible." (without the quotes, but with the dot.)

try this
Input:

Code: Select all

1 1
1
1 1
0
1 1
0
1
1 1 1
1 1
0
1
1 1 0
1 2
1
1 1
0
1 2
1
1 2
0
1 2
0
1
1 2 0
5 5
0
1
3 3 2
5 5
0
1
4 2 2
10 10
0
1
3 5 3
5 5
5
1 2
1 3
1 4
1 5
2 5
1
4 3 1
5 5
6
1 2
1 3
1 4
1 5
2 5
3 5
1
4 3 1
6 7
3
4 5
5 4
6 6
2
2 6 1
3 2 1
5 5
5
1 1
1 3
1 4
1 5
2 5
1
4 3 1
5 5
5
5 5
1 3
1 4
1 5
2 5
1
4 3 1
10 10
4
1 5
2 3
4 1
8 10
4
3 2 0
5 6 3
10 1 4
10 8 1
15 15
0
1
7 7 6
10 10
4
1 5
2 3
4 1
8 10
4
3 2 0
5 6 3
10 1 4
10 8 1
10 10
0
4
3 2 0
5 6 3
10 1 4
10 8 1
0 0

Output:

Code: Select all

0
0
0
1
Impossible.
Impossible.
Impossible.
8
18
8
Impossible.
15
8
Impossible.
Impossible.
Impossible.
Impossible.
18

[brianfry713]

Input:

Code: Select all

184 87
7
122 26
107 62
58 25
179 29
99 77
148 32
85 53
6
132 74 73
142 73 69
31 18 83
120 17 24
167 46 30
144 63 59
194 57
1
60 17
3
103 21 22
121 48 38
56 34 16
127 92
0
6
19 63 74
2 50 97
3 49 26
109 14 37
100 86 30
25 16 25
146 15
7
103 15
63 4
75 8
101 7
25 9
18 4
136 15
2
83 12 61
15 8 40
187 95
9
136 21
8 40
41 8
151 23
130 88
35 93
8 72
1 2
88 71
4
146 11 20
165 73 32
168 87 72
55 88 10
57 98
3
24 51
15 93
36 82
8
27 89 72
37 40 4
21 95 69
10 38 41
47 47 24
20 6 47
35 54 56
29 15 65
151 194
0
4
124 183 65
111 153 88
148 132 92
20 45 60
152 38
8
144 32
2 9
28 35
14 12
138 2
141 3
36 28
82 19
6
76 34 5
119 9 14
131 21 41
114 27 29
85 8 18
103 32 25
184 91
9
6 88
127 42
84 68
123 9
179 61
105 47
132 20
29 64
12 33
2
64 21 29
101 16 47
23 112
0
5
7 30 2
18 106 79
2 101 37
19 26 23
4 59 17
125 38
2
101 17
78 23
9
94 29 80
7 38 72
59 1 82
39 9 95
25 26 100
24 20 97
66 3 14
92 21 96
91 3 85
85 177
2
23 151
37 148
9
63 114 19
70 38 49
66 150 10
62 27 43
38 173 2
25 95 22
20 16 100
31 98 40
69 36 68
128 151
4
17 12
119 109
21 1
63 137
4
121 78 93
106 49 51
81 16 23
106 42 43
99 191
4
90 77
19 183
40 153
51 66
4
34 60 80
2 30 77
99 149 61
95 120 85
22 168
4
22 62
9 27
19 124
19 35
6
17 110 85
22 121 69
1 61 73
21 109 99
20 81 54
13 134 34
91 155
7
24 17
20 90
89 67
41 83
42 26
91 24
78 68
2
53 56 87
21 66 97
158 130
6
139 11
59 122
69 15
23 78
1 9
137 93
7
158 94 100
112 69 3
130 42 1
140 120 39
106 105 36
96 86 93
38 40 5
165 86
9
11 14
26 58
57 57
130 6
74 14
6 57
55 50
146 34
6 81
1
18 61 70
62 43
0
7
32 31 24
20 16 10
46 30 97
49 18 35
21 31 25
3 8 69
5 33 13
147 127
4
90 94
101 63
26 107
77 121
1
80 32 81
58 28
2
9 7
17 16
0
13 80
0
9
11 35 90
11 61 42
7 49 88
5 11 67
11 18 57
13 10 61
12 20 6
5 66 19
6 59 74
38 90
3
35 68
23 58
14 82
0
60 19
8
49 8
54 16
2 4
19 15
20 4
20 19
44 14
35 7
3
23 7 48
33 15 83
16 16 92
122 158
4
66 96
38 38
32 2
69 17
0
99 126
1
92 17
2
27 100 32
59 111 5
19 22
0
2
10 16 13
2 11 86
177 84
7
7 68
79 53
156 16
27 83
109 65
91 66
147 58
1
131 63 6
176 156
4
9 110
135 94
147 94
151 75
7
167 58 31
31 74 27
99 108 54
116 22 15
32 151 78
159 52 89
138 103 33
147 36
7
107 28
2 12
58 21
147 8
143 19
81 1
35 12
8
3 25 31
4 22 62
79 22 90
116 30 52
97 36 69
57 28 7
95 33 50
94 20 27
197 182
5
65 123
183 26
32 155
108 5
188 47
1
29 29 71
28 35
0
3
7 4 73
11 23 64
3 34 31
60 123
7
43 42
13 85
35 23
39 28
21 85
20 23
43 105
3
44 68 42
43 53 25
22 118 55
58 166
7
9 130
19 56
32 38
58 158
22 160
29 71
35 90
4
45 33 9
3 113 92
32 17 16
23 58 90
11 17
4
4 6
5 5
2 14
7 4
8
9 3 90
5 8 48
10 17 32
9 17 82
2 12 80
1 9 51
9 16 58
1 4 82
34 183
1
30 7
6
3 158 26
18 154 93
8 160 33
8 65 7
10 40 9
10 44 63
177 155
7
31 55
12 103
16 22
14 44
88 83
152 146
44 46
0
184 115
6
165 87
46 58
144 9
59 1
113 77
116 14
7
158 103 29
41 61 11
91 76 26
17 39 38
183 49 23
44 13 58
72 10 27
52 150
0
8
25 99 40
14 144 11
52 127 91
44 32 53
22 150 78
50 53 67
29 86 42
36 135 99
177 6
6
12 5
3 5
71 6
62 4
100 5
72 2
5
155 2 98
105 1 28
137 5 94
99 4 35
6 4 86
162 163
2
149 12
47 14
2
88 80 83
76 34 55
107 52
4
36 47
26 28
13 50
84 16
1
11 48 81
191 142
0
2
97 88 66
88 88 18
152 113
0
6
21 4 39
139 57 90
48 44 5
27 95 42
107 110 70
17 46 57
50 15
5
27 10
34 12
20 10
3 11
44 2
0
90 110
1
45 94
5
18 66 49
39 104 14
6 46 50
27 49 94
74 44 61
87 172
8
38 90
19 26
6 2
32 44
30 137
26 8
69 95
1 92
9
45 126 45
86 41 52
24 94 20
50 133 5
57 39 76
75 65 68
60 155 30
81 119 32
85 115 8
184 178
7
38 49
135 156
46 154
113 26
78 55
119 26
21 77
3
66 119 86
72 122 31
155 149 99
25 120
0
1
6 11 3
127 184
9
30 37
56 100
127 14
36 168
58 37
36 171
71 72
21 55
59 100
1
121 136 81
100 25
8
87 5
33 20
11 20
31 24
64 9
80 13
50 20
52 25
9
31 18 65
50 16 87
82 12 16
34 10 12
88 23 88
20 19 74
45 5 43
60 15 25
54 19 64
113 70
5
11 15
48 10
17 40
36 6
100 54
0
88 3
7
2 1
30 1
73 3
38 2
52 3
5 2
83 3
5
58 3 44
40 3 29
35 3 1
32 1 88
26 3 90
27 149
4
4 145
21 134
15 84
24 51
0
167 195
4
4 9
138 39
33 58
65 87
9
71 192 66
19 121 70
84 72 23
132 195 70
38 33 77
122 161 41
87 62 73
3 137 28
159 91 13
125 134
3
125 95
45 19
116 11
1
63 80 43
64 199
0
9
16 199 3
61 35 29
28 134 72
32 154 39
45 86 41
15 148 27
41 194 26
39 68 46
44 150 40
4 62
5
1 15
3 20
1 31
4 31
2 25
7
3 17 20
1 1 93
2 43 80
3 24 36
2 32 8
1 55 71
4 56 85
1 93
9
1 51
1 87
1 61
1 42
1 62
1 23
1 4
1 41
1 68
2
1 91 26
1 50 48
132 162
9
38 152
4 69
108 13
110 78
33 104
52 100
35 28
31 93
93 155
8
65 15 87
96 97 64
56 128 11
83 61 43
35 55 26
10 67 54
81 32 49
1 147 17
160 78
0
3
124 69 98
28 24 36
35 12 99
62 107
4
16 27
1 6
44 65
32 86
0
182 15
5
51 13
179 3
180 15
150 9
41 10
4
28 1 86
27 6 87
12 7 93
156 13 70
167 116
5
113 26
145 77
151 86
11 61
167 3
3
165 97 1
28 60 17
118 41 45
27 119
5
18 5
15 50
27 77
26 63
1 91
2
22 60 35
26 95 35
16 185
6
7 150
12 146
2 77
14 54
6 8
14 173
0
89 80
0
1
63 45 94
136 109
2
63 73
68 82
6
12 51 12
61 79 88
70 73 91
113 27 34
134 66 95
101 10 55
76 124
8
28 20
44 42
73 110
42 70
48 48
64 74
49 91
51 22
7
73 96 73
48 124 12
62 29 58
49 74 40
68 56 15
51 33 19
12 17 84
98 1
7
64 1
29 1
41 1
80 1
73 1
52 1
2 1
5
3 1 23
40 1 44
37 1 67
5 1 54
57 1 21
88 184
0
1
22 174 27
128 79
8
35 45
127 74
44 47
125 47
105 27
96 19
69 73
60 48
3
39 72 64
63 75 69
41 19 61
10 174
3
5 152
8 120
4 40
9
3 29 97
10 35 81
5 54 56
10 61 67
4 71 82
2 49 2
10 139 14
6 3 23
1 101 62
72 124
3
57 109
39 5
13 33
4
31 12 8
30 99 26
11 37 59
31 35 61
174 138
5
136 65
14 35
157 12
11 77
20 31
8
99 2 57
114 76 69
123 14 29
126 67 75
58 34 11
75 32 90
19 7 27
25 82 100
163 58
2
75 29
92 2
9
103 26 98
27 24 29
79 30 71
125 31 81
86 30 34
71 39 1
79 57 86
72 15 91
69 56 48
62 95
2
34 41
61 9
0
155 139
2
26 101
20 121
5
1 39 9
28 129 9
128 72 46
68 81 88
83 56 36
149 97
6
127 27
105 91
96 24
121 48
94 94
91 86
7
33 8 89
40 49 98
140 16 95
72 2 83
33 5 70
87 50 18
82 15 100
151 37
0
2
113 17 43
130 1 24
112 170
0
0
191 103
5
12 50
149 40
9 71
122 98
105 66
1
112 15 75
178 167
6
154 123
128 76
16 19
150 89
59 27
98 95
0
168 187
6
88 56
119 72
140 20
14 112
128 128
117 37
6
134 75 35
7 46 96
33 123 32
6 13 31
88 166 43
71 71 62
170 196
3
52 120
151 188
168 137
0
89 62
6
2 49
41 55
2 9
23 37
80 14
27 24
7
67 50 24
10 34 52
24 46 47
54 23 30
53 32 50
53 2 90
13 13 64
185 195
9
17 27
52 135
19 85
165 16
86 55
96 146
37 186
106 132
184 173
8
54 180 65
50 160 54
28 142 70
157 73 6
13 80 43
31 36 66
5 13 66
152 158 8
159 2
2
93 1
57 1
7
124 1 15
69 1 59
145 2 70
44 2 28
116 2 14
26 2 61
127 2 93
113 8
3
39 2
44 2
51 1
6
91 4 11
69 2 70
75 2 91
11 1 70
8 1 83
68 6 96
188 165
7
9 37
153 96
12 24
119 44
26 92
2 131
183 60
6
92 147 90
73 32 96
89 141 4
94 31 83
35 111 49
163 147 6
68 64
4
53 31
45 11
8 58
20 54
1
55 25 52
52 92
8
28 48
20 9
41 46
22 17
11 36
10 83
42 53
45 37
3
24 32 73
9 15 34
52 69 41
137 59
0
8
14 54 47
96 34 95
63 3 51
130 9 54
77 41 56
14 46 20
8 23 45
127 35 30
171 195
5
102 14
81 84
4 24
110 149
1 46
7
87 9 8
135 80 79
5 194 59
30 118 8
157 78 11
87 61 9
29 172 3
107 147
3
35 4
20 88
94 68
8
21 80 93
92 112 72
104 19 82
33 31 89
52 113 52
87 119 60
56 15 15
79 6 73
130 112
4
75 79
99 98
17 66
41 7
8
45 70 87
16 99 26
129 42 40
44 85 59
66 31 56
85 36 90
76 21 47
21 99 94
151 121
9
67 53
116 38
52 92
106 98
145 117
31 49
112 12
58 54
32 118
8
48 119 61
52 80 7
23 79 100
40 35 2
88 81 30
140 82 87
13 29 80
44 77 90
48 54
5
45 23
32 42
8 17
36 19
17 21
2
1 40 33
18 47 62
42 32
3
15 19
39 23
8 2
3
40 3 59
4 4 54
39 3 18
81 181
1
47 166
5
6 18 39
73 29 53
44 70 46
78 44 57
19 74 3
0 0

AC output:

Code: Select all

Impossible.
Impossible.
Impossible.
Impossible.
Impossible.
Impossible.
Impossible.
Impossible.
273
Impossible.
Impossible.
Impossible.
Impossible.
Impossible.
Impossible.
Impossible.
Impossible.
Impossible.
Impossible.
Impossible.
84
Impossible.
126
Impossible.
278
223
Impossible.
259
Impossible.
Impossible.
Impossible.
Impossible.
Impossible.
Impossible.
Impossible.
Impossible.
330
Impossible.
Impossible.
Impossible.
Impossible.
Impossible.
331
Impossible.
63
Impossible.
Impossible.
Impossible.
143
Impossible.
Impossible.
181
Impossible.
174
Impossible.
257
Impossible.
Impossible.
Impossible.
Impossible.
Impossible.
167
Impossible.
281
Impossible.
199
Impossible.
Impossible.
Impossible.
Impossible.
270
Impossible.
Impossible.
Impossible.
Impossible.
Impossible.
155
Impossible.
Impossible.
Impossible.
280
292
343
Impossible.
364
Impossible.
Impossible.
Impossible.
Impossible.
Impossible.
Impossible.
Impossible.
Impossible.
364
Impossible.
Impossible.
Impossible.
Impossible.
Impossible.
Impossible.

[Shahidul.CSE]

I have checked the output for the input given by brianfry713, outsbook and tan_Yui on uDebug.com . but I have noticed some differences for some cases between their output and output produced by uDebug.com . So, which one should I consider as correct and which one is wrong? or both are correct ??

[uDebug]

I have checked the output for the input given by brianfry713, outsbook and tan_Yui on uDebug.com . but I have noticed some differences for some cases between their output and output produced by uDebug.com . So, which one should I consider as correct and which one is wrong? or both are correct ??

The output produced by brianfry713 is indeed correct. This has now been fixed on uDebug as well. Please see

http://www.udebug.com/UVa/10977