2112.md (7469B)
1 Source: https://codeforces.com/blog/entry/144148 2 3 [2112A - Race](/contest/2112/problem/A "Educational Codeforces Round 180 (Rated for Div. 2)") 4 5 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 6 7 **Tutorial** 8 9 Tutorial is loading... 10 11 **Solution (Neon)** 12 13 ``` 14 #include <bits/stdc++.h> 15 16 using namespace std; 17 18 int main() { 19 int t; 20 cin >> t; 21 while (t--) { 22 int a, x, y; 23 cin >> a >> x >> y; 24 cout << ((a < x) == (a < y) ? "YES" : "NO") << '\n'; 25 } 26 } 27 ``` 28 29 [2112B - Shrinking Array](/contest/2112/problem/B "Educational Codeforces Round 180 (Rated for Div. 2)") 30 31 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 32 33 **Tutorial** 34 35 Tutorial is loading... 36 37 **Solution (adedalic)** 38 39 ``` 40 #include<bits/stdc++.h> 41 42 using namespace std; 43 44 void solve() { 45 int n; 46 cin >> n; 47 vector<int> a(n); 48 for (int i = 0; i < n; i++) 49 cin >> a[i]; 50 51 for (int i = 1; i < n; i++) { 52 if (abs(a[i - 1] - a[i]) <= 1) { 53 cout << 0 << endl; 54 return; 55 } 56 } 57 for (int i = 1; i + 1 < n; i++) { 58 if (a[i - 1] < a[i] && a[i] > a[i + 1]) { 59 cout << 1 << endl; 60 return; 61 } 62 if (a[i - 1] > a[i] && a[i] < a[i + 1]) { 63 cout << 1 << endl; 64 return; 65 } 66 } 67 cout << -1 << endl; 68 } 69 70 int main() { 71 #ifdef _DEBUG 72 freopen("input.txt", "r", stdin); 73 int tt = clock(); 74 #endif 75 int t; 76 cin >> t; 77 while (t--) { 78 solve(); 79 } 80 return 0; 81 } 82 ``` 83 84 [2112C - Coloring Game](/contest/2112/problem/C "Educational Codeforces Round 180 (Rated for Div. 2)") 85 86 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 87 88 **Tutorial** 89 90 Tutorial is loading... 91 92 **Solution (Neon)** 93 94 ``` 95 #include <bits/stdc++.h> 96 97 using namespace std; 98 99 int main() { 100 int t; 101 cin >> t; 102 while (t--) { 103 int n; 104 cin >> n; 105 vector<int> a(n); 106 for (auto& x : a) cin >> x; 107 long long ans = 0; 108 for (int i = 0; i < n; ++i) { 109 for (int j = 0; j < i; ++j) { 110 int x = max(a[n - 1], 2 * a[i]) - a[i] - a[j]; 111 int k = upper_bound(a.begin(), a.begin() + j, x) - a.begin(); 112 ans += j - k; 113 } 114 } 115 cout << ans << '\n'; 116 } 117 } 118 ``` 119 120 [2112D - Reachability and Tree](/contest/2112/problem/D "Educational Codeforces Round 180 (Rated for Div. 2)") 121 122 Idea: [adedalic](/profile/adedalic "International Master adedalic") 123 124 **Tutorial** 125 126 Tutorial is loading... 127 128 **Solution (adedalic)** 129 130 ``` 131 #include<bits/stdc++.h> 132 133 using namespace std; 134 135 #define fore(i, l, r) for(int i = int(l); i < int(r); i++) 136 #define sz(a) int((a).size()) 137 138 const int N = int(2e5) + 5; 139 140 int n; 141 vector<int> g[N]; 142 143 inline bool read() { 144 if(!(cin >> n)) 145 return false; 146 fore (i, 0, n) 147 g[i].clear(); 148 149 fore (i, 0, n - 1) { 150 int u, v; 151 cin >> u >> v; 152 u--, v--; 153 g[u].push_back(v); 154 g[v].push_back(u); 155 } 156 return true; 157 } 158 159 vector<int> used; 160 vector<pair<int, int>> ans; 161 162 void dfs(int v, bool in) { 163 used[v] = 1; 164 for (int to : g[v]) { 165 if (used[to]) 166 continue; 167 if (in) 168 ans.emplace_back(to, v); 169 else 170 ans.emplace_back(v, to); 171 dfs(to, !in); 172 } 173 } 174 175 inline void solve() { 176 int r = 0; 177 while (r < n && sz(g[r]) != 2) 178 r++; 179 if (r >= n) { 180 cout << "NO\n"; 181 return; 182 } 183 184 used.assign(n, 0); 185 ans.clear(); 186 187 ans.emplace_back(r, g[r][0]); 188 ans.emplace_back(g[r][1], r); 189 used[r] = 1; 190 191 dfs(g[r][0], true); 192 dfs(g[r][1], false); 193 194 cout << "YES\n"; 195 sort(ans.begin(), ans.end()); 196 for (auto [u, v] : ans) 197 cout << u + 1 << " " << v + 1 << '\n'; 198 } 199 200 int main() { 201 #ifdef _DEBUG 202 freopen("input.txt", "r", stdin); 203 int tt = clock(); 204 #endif 205 ios_base::sync_with_stdio(false); 206 cin.tie(0), cout.tie(0); 207 cout << fixed << setprecision(15); 208 209 int t; cin >> t; 210 while (t--) { 211 read(); 212 solve(); 213 214 #ifdef _DEBUG 215 cerr << "TIME = " << clock() - tt << endl; 216 tt = clock(); 217 #endif 218 } 219 return 0; 220 } 221 ``` 222 223 [2112E - Tree Colorings](/contest/2112/problem/E "Educational Codeforces Round 180 (Rated for Div. 2)") 224 225 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 226 227 **Tutorial** 228 229 Tutorial is loading... 230 231 **Solution in M sqrt M (Neon)** 232 233 ``` 234 #include <bits/stdc++.h> 235 236 using namespace std; 237 238 const int M = 5e5; 239 const int INF = 1e9; 240 241 int main() { 242 vector<int> dp(M + 1, INF); 243 dp[1] = 1; 244 for (int m = 2; m <= M; ++m) { 245 for (int i = 1; i * i <= m; ++i) { 246 if (m % i != 0) continue; 247 if (m / i > 2) dp[m] = min(dp[m], dp[i] + dp[m / i - 2]); 248 if (i > 2) dp[m] = min(dp[m], dp[m / i] + dp[i - 2]); 249 } 250 } 251 252 int q; 253 cin >> q; 254 while (q--) { 255 int m; 256 cin >> m; 257 cout << (dp[m] == INF ? -1 : dp[m]) << '\n'; 258 } 259 } 260 ``` 261 262 **Solution in M log M (BledDest)** 263 264 ``` 265 #include<bits/stdc++.h> 266 267 using namespace std; 268 269 const int N = 500043; 270 271 vector<int> divisors[N]; 272 273 int dp[N], dp2[N]; 274 275 int calc(int x); 276 277 int calc2(int x) 278 { 279 if(dp2[x] != -1) return dp2[x]; 280 if(x == 1) return dp2[x] = 0; 281 dp2[x] = calc(x); 282 for(auto y : divisors[x]) dp2[x] = min(dp2[x], calc(y) + calc2(x / y)); 283 return dp2[x]; 284 } 285 286 int calc(int x) 287 { 288 if(dp[x] != -1) return dp[x]; 289 if(x == 1) return dp[x] = 0; 290 if(x == 3) return dp[x] = 1; 291 return dp[x] = calc2(x - 2) + 1; 292 } 293 294 int main() 295 { 296 ios_base::sync_with_stdio(0); 297 cin.tie(0); 298 for(int i = 2; i < N; i++) 299 for(int j = i * 2; j < N; j += i) 300 divisors[j].push_back(i); 301 for(int i = 0; i < N; i++) dp[i] = dp2[i] = -1; 302 303 int t; 304 cin >> t; 305 for(int i = 0; i < t; i++) 306 { 307 int x; 308 cin >> x; 309 if(x % 2 == 0) cout << -1 << endl; 310 else cout << calc(x + 2) << endl; 311 } 312 return 0; 313 } 314 ``` 315 316 [2112F - Variables and Operations](/contest/2112/problem/F "Educational Codeforces Round 180 (Rated for Div. 2)") 317 318 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 319 320 **Tutorial** 321 322 Tutorial is loading... 323 324 **Solution (BledDest)** 325 326 ``` 327 #include<bits/stdc++.h> 328 329 using namespace std; 330 331 const int N = 543; 332 const long long INF64 = (long long)(1e18); 333 334 long long e[N][N]; 335 long long d[N][N]; 336 int n, m; 337 338 int main() 339 { 340 ios_base::sync_with_stdio(0); 341 cin.tie(0); 342 cin >> n >> m; 343 for(int i = 0; i < n; i++) 344 for(int j = 0; j < n; j++) 345 if(i != j) e[i][j] = INF64; 346 for(int i = 0; i < m; i++) 347 { 348 int x, y, w; 349 cin >> x >> y >> w; 350 --x; 351 --y; 352 swap(x, y); 353 e[x][y] = min(e[x][y], (long long)w); 354 } 355 for(int i = 0; i < n; i++) 356 for(int j = 0; j < n; j++) 357 d[i][j] = e[i][j]; 358 for(int k = 0; k < n; k++) 359 for(int i = 0; i < n; i++) 360 for(int j = 0; j < n; j++) 361 d[i][j] = min(d[i][j], d[i][k] + d[k][j]); 362 363 int q; 364 cin >> q; 365 for(int i = 0; i < q; i++) 366 { 367 long long op; 368 cin >> op; 369 vector<long long> a(n); 370 for(int j = 0; j < n; j++) cin >> a[j]; 371 vector<long long> min_dist = a; 372 vector<long long> min_one_edge = a; 373 for(int j = 0; j < n; j++) 374 for(int k = 0; k < n; k++) 375 { 376 min_dist[k] = min(min_dist[k], a[j] + d[j][k]); 377 min_one_edge[k] = min(min_one_edge[k], a[j] + e[j][k]); 378 } 379 vector<long long> min_op(n, INF64); 380 for(int j = 0; j < n; j++) 381 for(int k = 0; k < n; k++) 382 { 383 if(d[j][k] < e[j][k]) min_op[k] = min(min_op[k], (d[j][k] + a[j]) - (min_one_edge[k] - 1)); 384 } 385 for(int j = 0; j < n; j++) 386 { 387 if(min_op[j] <= op) cout << 1; 388 else cout << 0; 389 } 390 cout << endl; 391 } 392 393 return 0; 394 } 395 ```