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