1249.md (10051B)
1 Source: https://codeforces.com/blog/entry/70779 2 3 All ideas belong to [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov"). 4 5 [1249A - Yet Another Dividing into Teams](/contest/1249/problem/A "Codeforces Round 595 (Div. 3)") 6 7 **Tutorial** 8 9 Tutorial is loading... 10 11 **Solution** 12 13 ``` 14 #include <bits/stdc++.h> 15 16 using namespace std; 17 18 int main() { 19 #ifdef _DEBUG 20 freopen("input.txt", "r", stdin); 21 // freopen("output.txt", "w", stdout); 22 #endif 23 24 int q; 25 cin >> q; 26 for (int i = 0; i < q; ++i) { 27 int n; 28 cin >> n; 29 vector<int> a(n); 30 for (int j = 0; j < n; ++j) { 31 cin >> a[j]; 32 } 33 bool ok = true; 34 for (int p1 = 0; p1 < n; ++p1) { 35 for (int p2 = 0; p2 < p1; ++p2) { 36 ok &= abs(a[p1] - a[p2]) != 1; 37 } 38 } 39 cout << 2 - ok << endl; 40 } 41 42 return 0; 43 } 44 ``` 45 46 [1249B1 - Books Exchange (easy version)](/contest/1249/problem/B1 "Codeforces Round 595 (Div. 3)") 47 48 **Tutorial** 49 50 Tutorial is loading... 51 52 **Solution** 53 54 ``` 55 #include <bits/stdc++.h> 56 57 using namespace std; 58 59 int main() { 60 #ifdef _DEBUG 61 freopen("input.txt", "r", stdin); 62 // freopen("output.txt", "w", stdout); 63 #endif 64 65 int q; 66 cin >> q; 67 for (int i = 0; i < q; ++i) { 68 int n; 69 cin >> n; 70 vector<int> p(n); 71 for (int j = 0; j < n; ++j) { 72 cin >> p[j]; 73 --p[j]; 74 } 75 for (int j = 0; j < n; ++j) { 76 int cnt = 0; 77 int k = j; 78 do { 79 ++cnt; 80 k = p[k]; 81 } while (k != j); 82 cout << cnt << " "; 83 } 84 cout << endl; 85 } 86 87 return 0; 88 } 89 ``` 90 91 [1249B2 - Books Exchange (hard version)](/contest/1249/problem/B2 "Codeforces Round 595 (Div. 3)") 92 93 **Tutorial** 94 95 Tutorial is loading... 96 97 **Solution** 98 99 ``` 100 #include <bits/stdc++.h> 101 102 using namespace std; 103 104 int main() { 105 #ifdef _DEBUG 106 freopen("input.txt", "r", stdin); 107 // freopen("output.txt", "w", stdout); 108 #endif 109 110 int q; 111 cin >> q; 112 for (int i = 0; i < q; ++i) { 113 int n; 114 cin >> n; 115 vector<int> p(n); 116 for (int j = 0; j < n; ++j) { 117 cin >> p[j]; 118 --p[j]; 119 } 120 vector<int> used(n); 121 vector<int> ans(n); 122 for (int j = 0; j < n; ++j) { 123 if (!used[j]) { 124 vector<int> cur; 125 while (!used[j]) { 126 cur.push_back(j); 127 used[j] = true; 128 j = p[j]; 129 } 130 for (auto el : cur) ans[el] = cur.size(); 131 } 132 } 133 for (int j = 0; j < n; ++j) cout << ans[j] << " "; 134 cout << endl; 135 } 136 137 return 0; 138 } 139 ``` 140 141 [1249C1 - Good Numbers (easy version)](/contest/1249/problem/C1 "Codeforces Round 595 (Div. 3)") 142 143 **Tutorial** 144 145 Tutorial is loading... 146 147 **Solution** 148 149 ``` 150 #include <bits/stdc++.h> 151 152 using namespace std; 153 154 int main() { 155 #ifdef _DEBUG 156 freopen("input.txt", "r", stdin); 157 // freopen("output.txt", "w", stdout); 158 #endif 159 160 int q; 161 cin >> q; 162 for (int i = 0; i < q; ++i) { 163 int n; 164 cin >> n; 165 while (true) { 166 bool ok = true; 167 int cur = n; 168 while (cur > 0) { 169 if (ok && cur % 3 == 2) ok = false; 170 cur /= 3; 171 } 172 if (ok) break; 173 ++n; 174 } 175 cout << n << endl; 176 } 177 178 return 0; 179 } 180 ``` 181 182 [1249C2 - Good Numbers (hard version)](/contest/1249/problem/C2 "Codeforces Round 595 (Div. 3)") 183 184 **Tutorial** 185 186 Tutorial is loading... 187 188 **Solution** 189 190 ``` 191 #include <bits/stdc++.h> 192 193 using namespace std; 194 195 const long long INF64 = 1e18; 196 197 int main() { 198 #ifdef _DEBUG 199 freopen("input.txt", "r", stdin); 200 // freopen("output.txt", "w", stdout); 201 #endif 202 203 int q; 204 cin >> q; 205 for (int i = 0; i < q; ++i) { 206 long long n; 207 cin >> n; 208 vector<int> vals; 209 int pos2 = -1; 210 while (n > 0) { 211 vals.push_back(n % 3); 212 if (vals.back() == 2) pos2 = int(vals.size()) - 1; 213 n /= 3; 214 } 215 vals.push_back(0); 216 if (pos2 != -1) { 217 int pos0 = find(vals.begin() + pos2, vals.end(), 0) - vals.begin(); 218 vals[pos0] = 1; 219 for (int i = pos0 - 1; i >= 0; --i) { 220 vals[i] = 0; 221 } 222 } 223 long long ans = 0; 224 long long pw = 1; 225 for (int i = 0; i < int(vals.size()); ++i) { 226 ans += pw * vals[i]; 227 pw *= 3; 228 } 229 if (vals.back() == 1) ans = pw / 3; 230 cout << ans << endl; 231 } 232 233 return 0; 234 } 235 ``` 236 237 [1249D1 - Too Many Segments (easy version)](/contest/1249/problem/D1 "Codeforces Round 595 (Div. 3)") 238 239 **Tutorial** 240 241 Tutorial is loading... 242 243 **Solution** 244 245 ``` 246 #include <bits/stdc++.h> 247 248 using namespace std; 249 250 const int N = 250; 251 252 int main() { 253 #ifdef _DEBUG 254 freopen("input.txt", "r", stdin); 255 // freopen("output.txt", "w", stdout); 256 #endif 257 258 int n, k; 259 cin >> n >> k; 260 vector<pair<int, int>> segs(n); 261 vector<int> cnt(N); 262 for (int i = 0; i < n; ++i) { 263 cin >> segs[i].first >> segs[i].second; 264 ++cnt[segs[i].first]; 265 --cnt[segs[i].second + 1]; 266 } 267 268 for (int i = 0; i + 1 < N; ++i) { 269 cnt[i + 1] += cnt[i]; 270 } 271 272 vector<int> ans(n); 273 for (int i = 0; i < N; ++i) { 274 while (cnt[i] > k) { 275 int pos = -1; 276 for (int p = 0; p < n; ++p) { 277 if (!ans[p] && (segs[p].first <= i && i <= segs[p].second) && (pos == -1 || segs[p].second > segs[pos].second)) { 278 pos = p; 279 } 280 } 281 assert(pos != -1); 282 for (int j = segs[pos].first; j <= segs[pos].second; ++j) { 283 --cnt[j]; 284 } 285 ans[pos] = 1; 286 } 287 } 288 289 cout << accumulate(ans.begin(), ans.end(), 0) << endl; 290 for (int i = 0; i < n; ++i) { 291 if (ans[i]) cout << i + 1 << " "; 292 } 293 cout << endl; 294 295 return 0; 296 } 297 ``` 298 299 [1249D2 - Too Many Segments (hard version)](/contest/1249/problem/D2 "Codeforces Round 595 (Div. 3)") 300 301 **Tutorial** 302 303 Tutorial is loading... 304 305 **Solution** 306 307 ``` 308 #include <bits/stdc++.h> 309 310 using namespace std; 311 312 const int N = 200200; 313 314 int main() { 315 #ifdef _DEBUG 316 freopen("input.txt", "r", stdin); 317 // freopen("output.txt", "w", stdout); 318 #endif 319 320 int n, k; 321 cin >> n >> k; 322 vector<pair<int, int>> segs(n); 323 vector<int> cnt(N); 324 vector<vector<int>> ev(N); 325 for (int i = 0; i < n; ++i) { 326 cin >> segs[i].first >> segs[i].second; 327 ++cnt[segs[i].first]; 328 --cnt[segs[i].second + 1]; 329 ev[segs[i].first].push_back(i + 1); 330 ev[segs[i].second + 1].push_back(-i - 1); 331 } 332 333 for (int i = 0; i + 1 < N; ++i) { 334 cnt[i + 1] += cnt[i]; 335 } 336 337 vector<int> ans(n), sub(N); 338 set<pair<int, int>> curSegs; 339 int curSub = 0; 340 for (int i = 0; i < N; ++i) { 341 curSub += sub[i]; 342 for (auto it : ev[i]) { 343 if (it > 0) { 344 curSegs.insert(make_pair(segs[it - 1].second, it - 1)); 345 } else { 346 auto iter = curSegs.find(make_pair(segs[-it - 1].second, -it - 1)); 347 if (iter != curSegs.end()) curSegs.erase(iter); 348 } 349 } 350 while (cnt[i] - curSub > k) { 351 assert(!curSegs.empty()); 352 int pos = curSegs.rbegin()->second; 353 curSegs.erase(prev(curSegs.end())); 354 ++curSub; 355 --sub[segs[pos].second + 1]; 356 ans[pos] = 1; 357 } 358 } 359 360 cout << accumulate(ans.begin(), ans.end(), 0) << endl; 361 for (int i = 0; i < n; ++i) { 362 if (ans[i]) cout << i + 1 << " "; 363 } 364 cout << endl; 365 366 return 0; 367 } 368 ``` 369 370 [1249E - By Elevator or Stairs?](/contest/1249/problem/E "Codeforces Round 595 (Div. 3)") 371 372 **Tutorial** 373 374 Tutorial is loading... 375 376 **Solution** 377 378 ``` 379 #include <bits/stdc++.h> 380 381 using namespace std; 382 383 const int INF = 1e9; 384 385 int main() { 386 #ifdef _DEBUG 387 freopen("input.txt", "r", stdin); 388 // freopen("output.txt", "w", stdout); 389 #endif 390 391 int n, c; 392 cin >> n >> c; 393 vector<int> a(n - 1), b(n - 1); 394 for (int i = 0; i < n - 1; ++i) { 395 cin >> a[i]; 396 } 397 for (int i = 0; i < n - 1; ++i) { 398 cin >> b[i]; 399 } 400 vector<vector<int>> dp(n, vector<int>(2, INF)); 401 dp[0][0] = 0, dp[0][1] = c; 402 for (int i = 0; i < n - 1; ++i) { 403 dp[i + 1][0] = min(dp[i + 1][0], dp[i][1] + a[i]); 404 dp[i + 1][0] = min(dp[i + 1][0], dp[i][0] + a[i]); 405 dp[i + 1][1] = min(dp[i + 1][1], dp[i][1] + b[i]); 406 dp[i + 1][1] = min(dp[i + 1][1], dp[i][0] + b[i] + c); 407 } 408 409 for (int i = 0; i < n; ++i) { 410 cout << min(dp[i][0], dp[i][1]) << " "; 411 } 412 cout << endl; 413 414 return 0; 415 } 416 ``` 417 418 [1249F - Maximum Weight Subset](/contest/1249/problem/F "Codeforces Round 595 (Div. 3)") 419 420 Thanks to [neal](/profile/neal "International Grandmaster neal") for the [additional editorial](https://codeforces.com/blog/entry/70822) of this problem and providing the linear solution! 421 422 **Tutorial** 423 424 Tutorial is loading... 425 426 **Solution (Vovuh, n^3)** 427 428 ``` 429 #include <bits/stdc++.h> 430 431 using namespace std; 432 433 const int N = 210; 434 435 int n, k; 436 vector<int> a; 437 vector<vector<int>> g, dp; 438 439 void dfs(int v, int p) { 440 dp[v][0] = a[v]; 441 for (auto to : g[v]) { 442 if (to != p) dfs(to, v); 443 } 444 for (int dep = 0; dep < N; ++dep) { 445 if (dep == 0) { 446 for (auto to : g[v]) { 447 if (to == p) continue; 448 dp[v][dep] += dp[to][max(0, k - dep - 1)]; 449 } 450 } else { 451 for (auto to : g[v]) { 452 if (to == p) continue; 453 int cur = dp[to][dep - 1]; 454 for (auto other : g[v]) { 455 if (other == p || other == to) continue; 456 cur += dp[other][max(dep - 1, k - dep - 1)]; 457 } 458 dp[v][dep] = max(dp[v][dep], cur); 459 } 460 } 461 } 462 for (int dep = N - 1; dep > 0; --dep) { 463 dp[v][dep - 1] = max(dp[v][dep - 1], dp[v][dep]); 464 } 465 } 466 467 int main() { 468 #ifdef _DEBUG 469 freopen("input.txt", "r", stdin); 470 // freopen("output.txt", "w", stdout); 471 #endif 472 473 cin >> n >> k; 474 ++k; 475 a = vector<int>(n); 476 for (int i = 0; i < n; ++i) { 477 cin >> a[i]; 478 } 479 g = vector<vector<int>>(n); 480 for (int i = 0; i < n - 1; ++i) { 481 int x, y; 482 cin >> x >> y; 483 --x, --y; 484 g[x].push_back(y); 485 g[y].push_back(x); 486 } 487 488 dp = vector<vector<int>>(n, vector<int>(N)); 489 dfs(0, -1); 490 cout << dp[0][0] << endl; 491 492 return 0; 493 } 494 ``` 495 496 **Solution (PikMike, n^2)** 497 498 ``` 499 #include <bits/stdc++.h> 500 501 using namespace std; 502 503 #define forn(i, n) for (int i = 0; i < int(n); ++i) 504 505 const int N = 200 + 13; 506 const int INF = 1e9; 507 508 int n, k; 509 int a[N]; 510 vector<int> g[N]; 511 int dp[N][N]; 512 int d[N]; 513 int tmp[N]; 514 515 void dfs(int v, int p = -1){ 516 d[v] = 1; 517 dp[v][0] = a[v]; 518 for (auto u : g[v]) if (u != p){ 519 dfs(u, v); 520 int nw = max(d[v], d[u] + 1); 521 forn(i, nw) 522 tmp[i] = -INF; 523 forn(i, d[v]) for (int j = max(0, k - i); j < d[u]; ++j) 524 tmp[min(i, j + 1)] = max(tmp[min(i, j + 1)], dp[v][i] + dp[u][j]); 525 forn(i, d[u]) 526 tmp[i + 1] = max(tmp[i + 1], dp[u][i]); 527 forn(i, d[v]) 528 dp[v][i] = max(dp[v][i], tmp[i]); 529 for (int i = d[v]; i < nw; ++i) 530 dp[v][i] = tmp[i]; 531 d[v] = nw; 532 for (int i = d[v] - 1; i > 0; --i) 533 dp[v][i - 1] = max(dp[v][i - 1], dp[v][i]); 534 } 535 } 536 537 int main(){ 538 scanf("%d%d", &n, &k); 539 forn(i, n) 540 scanf("%d", &a[i]); 541 forn(i, n - 1){ 542 int v, u; 543 scanf("%d%d", &v, &u); 544 --v, --u; 545 g[v].push_back(u); 546 g[u].push_back(v); 547 } 548 dfs(0); 549 printf("%d\n", dp[0][0]); 550 } 551 ```