fork download
copy 
  1. #pragma GCC optimize("O3", "unroll-loops")
  2.  
  3. #include <bits/stdc++.h>
  4. using namespace std;
  5.  
  6. #define int long long
  7. #define double long double
  8. using pii = pair<int, int>;
  9. template<typename T>
  10. using prior = std::priority_queue<T, vector<T>, greater<T>>;
  11. template<typename T>
  12. using Prior = std::priority_queue<T>;
  13.  
  14. #define X first
  15. #define Y second
  16. #define ALL(x) (x).begin(), (x).end()
  17. #define RALL(x) (x).rbegin(), (x).rend()
  18. #define eb emplace_back
  19. #define pb push_back
  20. #define fastIO() ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
  21.  
  22. const int INF = 1E9 + 7;
  23. const int maxn = 2000 + 5;
  24.  
  25. vector<int> adj[maxn], ans[maxn], val;
  26.  
  27. void dfs(int now, int lst) {
  28.     vector<vector<int>> ch;
  29.     for (auto x : adj[now]) {
  30.         if (x != lst) dfs(x, now), ch.eb(ans[x]);
  31.     }
  32.     sort(ALL(ch), [](auto v1, auto v2) {
  33.         int sz1 = v1.size(), sz2 = v2.size();
  34.         for (int i = 0; i < sz1 + sz2; ++i) {
  35.             int a = i < sz1 ? v1[i] : v2[i-sz1];
  36.             int b = i < sz2 ? v2[i] : v1[i-sz2];
  37.             if (a != b) return a < b;
  38.         }
  39.         return false;
  40.     });
  41.     ans[now].clear(), ans[now].eb(val[now]);
  42.     for (auto vec : ch) for (auto x : vec) ans[now].eb(x);
  43. }
  44.  
  45. void solve() {
  46.     int n; cin >> n, val.resize(n);
  47.  
  48.     int minVal = INF;
  49.     for (auto &x : val) cin >> x, minVal = min(minVal, x);
  50.  
  51.     for (int i = 0; i < n-1; ++i) {
  52.         int u, v; cin >> u >> v, --u, --v;
  53.         adj[u].eb(v), adj[v].eb(u);
  54.     }
  55.  
  56.     vector<int> minAns(n, INF);
  57.     for (int i = 0; i < n; ++i) {
  58.         if (val[i] != minVal) continue;
  59.         dfs(i, -1);
  60.         for (int j = 0; j < n; ++j) {
  61.             if (ans[i][j] != minAns[j]) {
  62.                 if (ans[i][j] < minAns[j]) minAns.swap(ans[i]);
  63.                 break;
  64.             }
  65.         }
  66.     }
  67.  
  68.     for (auto x : minAns) cout << x << " ";
  69.     cout << "\n";
  70. }
  71.  
  72. int32_t main() {
  73.     fastIO();
  74.  
  75.     int t = 1; // cin >> t;
  76.     while (t--) solve();
  77.  
  78.     return 0;
  79. }
  80.  
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
264
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264
17 165
197 110
5 91
252 187
81 132
179 84
132 15
41 230
124 235
164 10
130 208
206 178
3 121
122 190
44 101
203 231
233 61
112 203
170 186
2 7
80 175
215 45
257 34
61 81
105 128
101 145
22 196
38 225
147 33
148 244
47 133
118 197
204 61
241 19
145 38
127 120
180 55
49 262
229 24
166 248
107 202
8 164
10 180
108 26
139 36
4 19
150 6
178 172
263 27
66 47
133 210
28 61
251 95
258 47
76 124
239 101
235 102
232 189
211 117
161 216
36 206
192 136
68 19
158 74
74 248
183 216
100 183
188 73
18 184
246 76
67 28
238 187
193 264
189 264
234 243
244 105
177 245
225 242
116 162
156 115
69 198
89 178
176 39
125 113
224 2
151 70
71 16
198 138
231 108
201 69
154 71
230 238
218 146
213 113
92 49
14 216
98 82
33 62
190 140
194 29
111 172
217 174
106 245
223 184
75 200
146 113
32 179
37 161
114 60
237 253
77 229
9 171
97 160
209 8
184 92
53 98
129 67
48 17
110 262
119 88
60 158
134 63
227 64
260 69
42 118
39 127
104 160
55 239
262 95
168 75
208 233
214 62
29 262
12 260
54 250
25 22
24 220
143 117
191 207
243 104
13 60
31 169
131 116
1 65
165 208
123 250
202 186
256 227
120 201
171 176
46 57
51 176
62 20
40 237
84 169
182 173
72 161
221 101
253 34
185 172
175 183
220 114
226 235
254 23
136 175
88 240
103 250
142 214
207 117
94 112
50 38
85 196
172 195
138 109
128 210
27 250
216 102
126 114
43 33
261 235
95 17
174 66
200 115
210 84
109 149
7 136
59 232
70 146
250 18
144 129
35 192
162 69
16 9
242 28
79 76
173 202
205 79
83 176
87 56
163 9
26 244
56 45
34 47
186 163
160 5
6 202
228 2
212 90
149 140
65 9
21 105
113 69
121 34
141 10
248 264
15 88
23 127
245 104
199 213
236 262
57 232
195 56
90 134
117 84
181 111
153 138
140 88
96 41
137 259
102 248
93 84
86 256
167 64
249 173
45 62
222 259
152 133
247 175
255 223
99 246
82 109
19 124
169 68
115 140
64 182
155 220
73 110
30 39
159 237
11 125
196 225
219 95
187 263
52 230
259 81
135 70
78 250
20 242
91 82
240 253
63 196
157 132
58 103
stdout
copy 
1 65 9 16 71 154 163 186 170 202 6 150 107 173 182 64 167 227 256 86 249 171 176 39 30 127 23 254 120 201 69 113 125 11 146 70 135 151 218 213 199 162 116 131 198 138 109 82 91 5 160 97 104 243 234 245 106 177 98 53 149 140 88 15 132 81 61 28 67 129 144 242 20 62 33 43 147 45 56 87 195 172 111 181 178 89 206 36 139 185 215 214 142 225 38 50 145 101 44 221 239 55 180 10 141 164 8 209 196 22 25 63 134 90 212 85 204 233 208 130 165 17 48 95 219 251 262 29 194 49 92 184 18 250 27 263 187 238 230 41 96 52 252 54 78 103 58 123 223 255 110 73 188 197 118 42 236 259 137 222 157 119 240 253 34 47 66 174 217 133 152 210 84 93 117 143 207 191 211 169 31 68 19 4 124 76 79 205 246 99 235 102 216 14 161 37 72 183 100 175 80 136 7 2 224 228 192 35 247 248 74 158 60 13 114 126 220 24 229 77 155 166 264 189 232 57 46 59 193 226 261 241 179 32 128 105 21 244 26 108 231 203 112 94 148 258 121 3 257 237 40 159 115 156 200 75 168 190 122 153 260 12 51 83
https://ideone.com/Arc90a
language:
C++14 (gcc 8.3)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!