1783.md (14425B)
1 Source: https://codeforces.com/blog/entry/111194 2 3 [1783A - Make it Beautiful](/contest/1783/problem/A "Educational Codeforces Round 141 (Rated for Div. 2)") 4 5 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 6 7 **Tutorial** 8 9 Tutorial is loading... 10 11 **Solution (BledDest)** 12 13 ``` 14 t = int(input()) 15 for i in range(t): 16 n = int(input()) 17 a = list(map(int, input().split())) 18 if a[0] == a[n - 1]: 19 print('NO') 20 else: 21 print('YES') 22 print(a[n - 1], end = ' ') 23 print(*(a[0:n-1])) 24 ``` 25 26 [1783B - Matrix of Differences](/contest/1783/problem/B "Educational Codeforces Round 141 (Rated for Div. 2)") 27 28 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 29 30 **Tutorial** 31 32 Tutorial is loading... 33 34 **Solution (Neon)** 35 36 ``` 37 #include <bits/stdc++.h> 38 39 using namespace std; 40 41 #define forn(i, n) for (int i = 0; i < int(n); ++i) 42 43 int main() { 44 int t; 45 cin >> t; 46 while (t--) { 47 int n; 48 cin >> n; 49 vector<vector<int>> a(n, vector<int>(n)); 50 int l = 1, r = n * n, t = 0; 51 forn(i, n) { 52 forn(j, n) { 53 if (t) a[i][j] = l++; 54 else a[i][j] = r--; 55 t ^= 1; 56 } 57 if (i & 1) reverse(a[i].begin(), a[i].end()); 58 } 59 forn(i, n) forn(j, n) cout << a[i][j] << " \n"[j == n - 1]; 60 } 61 } 62 ``` 63 64 [1783C - Yet Another Tournament](/contest/1783/problem/C "Educational Codeforces Round 141 (Rated for Div. 2)") 65 66 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 67 68 **Tutorial** 69 70 Tutorial is loading... 71 72 **Solution (Neon)** 73 74 ``` 75 #include <bits/stdc++.h> 76 77 using namespace std; 78 79 int main() { 80 ios::sync_with_stdio(false); cin.tie(0); 81 int t; 82 cin >> t; 83 while (t--) { 84 int n, m; 85 cin >> n >> m; 86 vector<int> a(n); 87 for (auto &x : a) cin >> x; 88 auto b = a; 89 sort(b.begin(), b.end()); 90 int ans = 0; 91 for (int i = 0; i < n && b[i] <= m; ++i) { 92 m -= b[i]; 93 ++ans; 94 } 95 if (ans != 0 && ans != n && m + b[ans - 1] >= a[ans]) ++ans; 96 cout << n + 1 - ans << '\n'; 97 } 98 } 99 ``` 100 101 [1783D - Different Arrays](/contest/1783/problem/D "Educational Codeforces Round 141 (Rated for Div. 2)") 102 103 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 104 105 **Tutorial** 106 107 Tutorial is loading... 108 109 **Solution (BledDest)** 110 111 ``` 112 #include<bits/stdc++.h> 113 114 using namespace std; 115 116 const int MOD = 998244353; 117 118 int add(int x, int y) 119 { 120 x += y; 121 while(x >= MOD) x -= MOD; 122 while(x < 0) x += MOD; 123 return x; 124 } 125 126 const int ZERO = 100000; 127 128 int dp[2][ZERO * 2]; 129 130 void recalc(int x) 131 { 132 for(int i = 0; i < ZERO * 2; i++) 133 dp[1][i] = 0; 134 135 for(int i = 0; i < ZERO * 2; i++) 136 { 137 if(dp[0][i] == 0) continue; 138 int nx = x + i; 139 dp[1][nx] = add(dp[1][nx], dp[0][i]); 140 if(nx != ZERO) 141 dp[1][2 * ZERO - nx] = add(dp[1][2 * ZERO - nx], dp[0][i]); 142 } 143 144 for(int i = 0; i < ZERO * 2; i++) 145 dp[0][i] = dp[1][i]; 146 } 147 148 int main() 149 { 150 int n; 151 cin >> n; 152 vector<int> a(n); 153 for(int i = 0; i < n; i++) 154 cin >> a[i]; 155 dp[0][ZERO] = 1; 156 for(int i = 1; i + 1 < n; i++) 157 recalc(a[i]); 158 int ans = 0; 159 for(int i = 0; i < ZERO * 2; i++) 160 ans = add(ans, dp[0][i]); 161 cout << ans << endl; 162 } 163 ``` 164 165 [1783E - Game of the Year](/contest/1783/problem/E "Educational Codeforces Round 141 (Rated for Div. 2)") 166 167 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 168 169 **Tutorial** 170 171 Tutorial is loading... 172 173 **Solution (BledDest)** 174 175 ``` 176 #include <bits/stdc++.h> 177 178 #define forn(i, n) for (int i = 0; i < int(n); i++) 179 180 using namespace std; 181 182 int main() { 183 int t; 184 scanf("%d", &t); 185 while (t--){ 186 int n; 187 scanf("%d", &n); 188 vector<int> a(n), b(n); 189 forn(i, n) scanf("%d", &a[i]); 190 forn(i, n) scanf("%d", &b[i]); 191 vector<int> dx(n + 1); 192 forn(i, n) if (b[i] < a[i]){ 193 ++dx[b[i]]; 194 --dx[a[i]]; 195 } 196 forn(i, n) dx[i + 1] += dx[i]; 197 vector<int> ans; 198 for (int k = 1; k <= n; ++k){ 199 bool ok = true; 200 for (int nk = k; nk <= n; nk += k) 201 ok &= dx[nk] == 0; 202 if (ok) 203 ans.push_back(k); 204 } 205 printf("%d\n", int(ans.size())); 206 for (int k : ans) printf("%d ", k); 207 puts(""); 208 } 209 return 0; 210 } 211 ``` 212 213 [1783F - Double Sort II](/contest/1783/problem/F "Educational Codeforces Round 141 (Rated for Div. 2)") 214 215 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 216 217 **Tutorial** 218 219 Tutorial is loading... 220 221 **Solution (BledDest)** 222 223 ``` 224 #include<bits/stdc++.h> 225 226 using namespace std; 227 228 const int N = 5043; 229 230 vector<int> g[N]; 231 int mt[N]; 232 int u[N]; 233 vector<vector<int>> cycle[2]; 234 vector<int> a[2]; 235 int n; 236 int vs[2]; 237 vector<vector<int>> inter; 238 239 bool kuhn(int x) 240 { 241 if(u[x]) return false; 242 u[x] = true; 243 for(auto y : g[x]) 244 { 245 if(mt[y] == x) continue; 246 if(mt[y] == -1 || kuhn(mt[y])) 247 { 248 mt[y] = x; 249 return true; 250 } 251 } 252 return false; 253 } 254 255 int find_intersection(const vector<int>& x, const vector<int>& y) 256 { 257 for(auto i : x) 258 for(auto j : y) 259 if(i == j) 260 return i; 261 return -1; 262 } 263 264 int main() 265 { 266 scanf("%d", &n); 267 for(int k = 0; k < 2; k++) 268 { 269 a[k].resize(n); 270 for(int j = 0; j < n; j++) 271 { 272 scanf("%d", &a[k][j]); 273 a[k][j]--; 274 } 275 } 276 277 for(int k = 0; k < 2; k++) 278 { 279 vector<bool> used(n); 280 for(int i = 0; i < n; i++) 281 { 282 if(used[i]) continue; 283 vector<int> cur; 284 int j = i; 285 while(!used[j]) 286 { 287 cur.push_back(j); 288 used[j] = true; 289 j = a[k][j]; 290 } 291 cycle[k].push_back(cur); 292 } 293 vs[k] = cycle[k].size(); 294 } 295 296 inter.resize(vs[0], vector<int>(vs[1])); 297 298 for(int i = 0; i < vs[0]; i++) 299 for(int j = 0; j < vs[1]; j++) 300 { 301 inter[i][j] = find_intersection(cycle[0][i], cycle[1][j]); 302 if(inter[i][j] != -1) 303 g[i].push_back(j); 304 } 305 306 for(int i = 0; i < vs[1]; i++) 307 mt[i] = -1; 308 for(int i = 0; i < vs[0]; i++) 309 { 310 for(int j = 0; j < vs[0]; j++) 311 u[j] = false; 312 kuhn(i); 313 } 314 315 set<int> res; 316 for(int i = 0; i < n; i++) res.insert(i); 317 for(int i = 0; i < vs[1]; i++) 318 if(mt[i] != -1) 319 res.erase(inter[mt[i]][i]); 320 321 printf("%d\n", res.size()); 322 for(auto x : res) printf("%d ", x + 1); 323 puts(""); 324 } 325 ``` 326 327 [1783G - Weighed Tree Radius](/contest/1783/problem/G "Educational Codeforces Round 141 (Rated for Div. 2)") 328 329 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 330 331 **Tutorial** 332 333 Tutorial is loading... 334 335 **Solution 1 (adedalic)** 336 337 ``` 338 #include<bits/stdc++.h> 339 340 using namespace std; 341 342 #define fore(i, l, r) for(int i = int(l); i < int(r); i++) 343 #define sz(a) int((a).size()) 344 345 #define x first 346 #define y second 347 348 typedef long long li; 349 typedef long double ld; 350 typedef pair<int, int> pt; 351 352 template<class A, class B> ostream& operator <<(ostream& out, const pair<A, B> &p) { 353 return out << "(" << p.x << ", " << p.y << ")"; 354 } 355 template<class A> ostream& operator <<(ostream& out, const vector<A> &v) { 356 fore(i, 0, sz(v)) { 357 if(i) out << " "; 358 out << v[i]; 359 } 360 return out; 361 } 362 363 const int INF = int(1e9); 364 const li INF64 = li(1e18); 365 const ld EPS = 1e-9; 366 367 const int LOG = 18; 368 const int N = int(2e5) + 55; 369 370 int n; 371 vector<int> a; 372 vector<int> g[N]; 373 374 inline bool read() { 375 if(!(cin >> n)) 376 return false; 377 a.resize(n); 378 fore (i, 0, n) 379 cin >> a[i]; 380 fore (i, 0, n - 1) { 381 int u, v; 382 cin >> u >> v; 383 u--, v--; 384 g[u].push_back(v); 385 g[v].push_back(u); 386 } 387 return true; 388 } 389 390 int p[LOG][N]; 391 int h[N], tin[N], tout[N], T = 0; 392 393 void precalcLca(int v, int pr) { 394 tin[v] = T++; 395 h[v] = 0; 396 if (pr != v) 397 h[v] = h[pr] + 1; 398 p[0][v] = pr; 399 fore (pw, 0, LOG - 1) 400 p[pw + 1][v] = p[pw][p[pw][v]]; 401 402 for (int to : g[v]) { 403 if (to == pr) 404 continue; 405 precalcLca(to, v); 406 } 407 tout[v] = T; 408 } 409 410 bool isParent(int l, int v) { 411 return tin[l] <= tin[v] && tout[v] <= tout[l]; 412 } 413 414 int lca(int u, int v) { 415 if (isParent(u, v)) 416 return u; 417 if (isParent(v, u)) 418 return v; 419 420 for (int pw = LOG - 1; pw >= 0; pw--) 421 if (!isParent(p[pw][v], u)) 422 v = p[pw][v]; 423 assert(!isParent(v, u)); 424 assert(isParent(p[0][v], u)); 425 return p[0][v]; 426 } 427 428 int getFarthest(int s) { 429 vector<int> used(n, 0); 430 queue<int> q; 431 432 used[s] = 1; 433 q.push(s); 434 int v; 435 while (!q.empty()) { 436 v = q.front(); 437 q.pop(); 438 for (int to : g[v]) { 439 if (used[to]) 440 continue; 441 used[to] = 1; 442 q.push(to); 443 } 444 } 445 return v; 446 } 447 448 int getDist(int u, int v) { 449 return h[u] + h[v] - 2 * h[lca(u, v)]; 450 } 451 452 const int M = int(2e5); 453 vector<pt> ops[4 * M]; 454 455 void setOp(int v, int l, int r, int lf, int rg, const pt &op) { 456 if (l >= r || lf >= rg) return; 457 if (l == lf && r == rg) { 458 ops[v].push_back(op); 459 return; 460 } 461 int mid = (l + r) / 2; 462 if (lf < mid) 463 setOp(2 * v + 1, l, mid, lf, min(mid, rg), op); 464 if (rg > mid) 465 setOp(2 * v + 2, mid, r, max(lf, mid), rg, op); 466 } 467 468 void updDiam(int &s, int &t, int &curD, const pt &op) { 469 int v = op.x; 470 a[v] = op.y; 471 472 int ns = s, nt = t, nD = curD; 473 474 vector<pt> cds = {{s, v}, {v, t}, {v, v}}; 475 for (auto &c : cds) { 476 int d1 = getDist(c.x, c.y); 477 if (nD < a[c.x] + d1 + a[c.y]) { 478 nD = a[c.x] + d1 + a[c.y]; 479 ns = c.x, nt = c.y; 480 } 481 } 482 s = ns; 483 t = nt; 484 curD = nD; 485 } 486 487 vector<int> ans; 488 489 void calcDiams(int v, int l, int r, int s, int t, int curD) { 490 for (auto &op : ops[v]) 491 updDiam(s, t, curD, op); 492 if (r - l > 1) { 493 int mid = (l + r) / 2; 494 calcDiams(2 * v + 1, l, mid, s, t, curD); 495 calcDiams(2 * v + 2, mid, r, s, t, curD); 496 } 497 else 498 ans[l] = (curD + 1) / 2; 499 500 for (auto &op : ops[v]) 501 a[op.first] = 0; 502 } 503 504 inline void solve() { 505 precalcLca(0, 0); 506 int s = getFarthest(0); 507 int t = getFarthest(s); 508 509 int m; 510 cin >> m; 511 vector<int> lst(n, 0); 512 fore (i, 0, m) { 513 int v, x; 514 cin >> v >> x; 515 v--; 516 517 setOp(0, 0, m, lst[v], i, {v, a[v]}); 518 lst[v] = i; 519 a[v] = x; 520 } 521 fore (v, 0, n) 522 setOp(0, 0, m, lst[v], m, {v, a[v]}); 523 524 ans.resize(m, -1); 525 a.assign(n, 0); 526 calcDiams(0, 0, m, s, t, getDist(s, t)); 527 528 fore (i, 0, m) 529 cout << ans[i] << '\n'; 530 } 531 532 int main() { 533 #ifdef _DEBUG 534 freopen("input.txt", "r", stdin); 535 int tt = clock(); 536 #endif 537 ios_base::sync_with_stdio(false); 538 cin.tie(0), cout.tie(0); 539 cout << fixed << setprecision(15); 540 541 if(read()) { 542 solve(); 543 544 #ifdef _DEBUG 545 cerr << "TIME = " << clock() - tt << endl; 546 tt = clock(); 547 #endif 548 } 549 return 0; 550 } 551 ``` 552 553 **Solution 2 (adedalic)** 554 555 ``` 556 #include<bits/stdc++.h> 557 558 using namespace std; 559 560 #define fore(i, l, r) for(int i = int(l); i < int(r); i++) 561 #define sz(a) int((a).size()) 562 563 #define x first 564 #define y second 565 566 typedef long long li; 567 typedef long double ld; 568 typedef pair<int, int> pt; 569 570 template<class A, class B> ostream& operator <<(ostream& out, const pair<A, B> &p) { 571 return out << "(" << p.x << ", " << p.y << ")"; 572 } 573 template<class A> ostream& operator <<(ostream& out, const vector<A> &v) { 574 fore(i, 0, sz(v)) { 575 if(i) out << " "; 576 out << v[i]; 577 } 578 return out; 579 } 580 581 const int INF = int(1e9); 582 const li INF64 = li(1e18); 583 const ld EPS = 1e-9; 584 585 const int LOG = 18; 586 const int N = int(2e5) + 55; 587 588 int n; 589 vector<int> a; 590 vector<int> g[N]; 591 592 inline bool read() { 593 if(!(cin >> n)) 594 return false; 595 a.resize(n); 596 fore (i, 0, n) 597 cin >> a[i]; 598 fore (i, 0, n - 1) { 599 int u, v; 600 cin >> u >> v; 601 u--, v--; 602 g[u].push_back(v); 603 g[v].push_back(u); 604 } 605 return true; 606 } 607 608 struct Lca { 609 vector<int> log2, tin; 610 vector< vector<int> > hs; 611 int T = 0; 612 613 void dfs(int v, int p, int cdepth) { 614 tin[v] = T++; 615 hs[0][tin[v]] = cdepth; 616 for (int to : g[v]) { 617 if (to == p) 618 continue; 619 dfs(to, v, cdepth + 1); 620 hs[0][T++] = cdepth; 621 } 622 } 623 624 void init() { 625 log2.assign(2 * n, 0); 626 fore (i, 2, sz(log2)) 627 log2[i] = log2[i / 2] + 1; 628 hs.assign(log2.back() + 1, vector<int>(2 * n, INF)); 629 630 tin.assign(n, 0); 631 T = 0; 632 633 dfs(0, -1, 0); 634 assert(T < 2 * n); 635 636 fore (pw, 0, sz(hs) - 1) { 637 fore (i, 0, T - (1 << pw)) 638 hs[pw + 1][i] = min(hs[pw][i], hs[pw][i + (1 << pw)]); 639 } 640 } 641 642 int getMin(int u, int v) { 643 if (tin[u] > tin[v]) 644 swap(u, v); 645 int len = log2[tin[v] + 1 - tin[u]]; 646 int d = min(hs[len][tin[u]], hs[len][tin[v] + 1 - (1 << len)]); 647 // cerr << u << " " << v << ": " << d << endl; 648 return d; 649 } 650 inline int getH(int v) { 651 return hs[0][tin[v]]; 652 } 653 } lcaST; 654 655 int getFarthest(int s) { 656 vector<int> used(n, 0); 657 queue<int> q; 658 659 used[s] = 1; 660 q.push(s); 661 int v; 662 while (!q.empty()) { 663 v = q.front(); 664 q.pop(); 665 for (int to : g[v]) { 666 if (used[to]) 667 continue; 668 used[to] = 1; 669 q.push(to); 670 } 671 } 672 return v; 673 } 674 675 int getDist(int u, int v) { 676 return lcaST.getH(u) + lcaST.getH(v) - 2 * lcaST.getMin(u, v); 677 } 678 679 const int M = int(2e5); 680 vector<pt> ops[4 * M]; 681 682 void setOp(int v, int l, int r, int lf, int rg, const pt &op) { 683 if (l >= r || lf >= rg) return; 684 if (l == lf && r == rg) { 685 ops[v].push_back(op); 686 return; 687 } 688 int mid = (l + r) / 2; 689 if (lf < mid) 690 setOp(2 * v + 1, l, mid, lf, min(mid, rg), op); 691 if (rg > mid) 692 setOp(2 * v + 2, mid, r, max(lf, mid), rg, op); 693 } 694 695 void updDiam(int &s, int &t, int &curD, const pt &op) { 696 int v = op.x; 697 a[v] = op.y; 698 699 int ns = s, nt = t, nD = curD; 700 701 vector<pt> cds = {{s, v}, {v, t}, {v, v}}; 702 for (auto &c : cds) { 703 int d1 = getDist(c.x, c.y); 704 if (nD < a[c.x] + d1 + a[c.y]) { 705 nD = a[c.x] + d1 + a[c.y]; 706 ns = c.x, nt = c.y; 707 } 708 } 709 s = ns; 710 t = nt; 711 curD = nD; 712 } 713 714 vector<int> ans; 715 716 void calcDiams(int v, int l, int r, int s, int t, int curD) { 717 for (auto &op : ops[v]) 718 updDiam(s, t, curD, op); 719 if (r - l > 1) { 720 int mid = (l + r) / 2; 721 calcDiams(2 * v + 1, l, mid, s, t, curD); 722 calcDiams(2 * v + 2, mid, r, s, t, curD); 723 } 724 else 725 ans[l] = (curD + 1) / 2; 726 727 for (auto &op : ops[v]) 728 a[op.first] = 0; 729 } 730 731 inline void solve() { 732 lcaST.init(); 733 int s = getFarthest(0); 734 int t = getFarthest(s); 735 736 int m; 737 cin >> m; 738 vector<int> lst(n, 0); 739 fore (i, 0, m) { 740 int v, x; 741 cin >> v >> x; 742 v--; 743 744 setOp(0, 0, m, lst[v], i, {v, a[v]}); 745 lst[v] = i; 746 a[v] = x; 747 } 748 fore (v, 0, n) 749 setOp(0, 0, m, lst[v], m, {v, a[v]}); 750 751 ans.resize(m, -1); 752 a.assign(n, 0); 753 calcDiams(0, 0, m, s, t, getDist(s, t)); 754 755 fore (i, 0, m) 756 cout << ans[i] << '\n'; 757 } 758 759 int main() { 760 #ifdef _DEBUG 761 freopen("input.txt", "r", stdin); 762 int tt = clock(); 763 #endif 764 ios_base::sync_with_stdio(false); 765 cin.tie(0), cout.tie(0); 766 cout << fixed << setprecision(15); 767 768 if(read()) { 769 solve(); 770 771 #ifdef _DEBUG 772 cerr << "TIME = " << clock() - tt << endl; 773 tt = clock(); 774 #endif 775 } 776 return 0; 777 } 778 ```