1187.md (11085B)
1 Source: https://codeforces.com/blog/entry/68111 2 3 [1187A - Stickers and Toys](/contest/1187/problem/A "Educational Codeforces Round 67 (Rated for Div. 2)") 4 5 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 6 7 **Tutorial** 8 9 Tutorial is loading... 10 11 **Solution (adedalic)** 12 13 ``` 14 fun main(args: Array<String>) { 15 val tc = readLine()!!.toInt() 16 for (i in 1..tc) { 17 val (n, s, t) = readLine()!!.split(' ').map { it.toInt() } 18 println(maxOf(n - s, n - t) + 1) 19 } 20 } 21 ``` 22 23 [1187B - Letters Shop](/contest/1187/problem/B "Educational Codeforces Round 67 (Rated for Div. 2)") 24 25 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 26 27 **Tutorial** 28 29 Tutorial is loading... 30 31 **Solution (PikMike)** 32 33 ``` 34 #include <bits/stdc++.h> 35 36 #define forn(i, n) for (int i = 0; i < int(n); i++) 37 38 using namespace std; 39 40 int n, m; 41 string s, t; 42 vector<int> pos[26]; 43 44 int main() { 45 cin >> n >> s; 46 forn(i, n) 47 pos[s[i] - 'a'].push_back(i + 1); 48 49 cin >> m; 50 forn(i, m){ 51 cin >> t; 52 vector<int> cnt(26); 53 for (auto &c : t) 54 ++cnt[c - 'a']; 55 int ans = -1; 56 forn(j, 26) if (cnt[j] > 0) 57 ans = max(ans, pos[j][cnt[j] - 1]); 58 cout << ans << "\n"; 59 } 60 return 0; 61 } 62 ``` 63 64 [1187C - Vasya And Array](/contest/1187/problem/C "Educational Codeforces Round 67 (Rated for Div. 2)") 65 66 Idea: [Roms](/profile/Roms "Master Roms") 67 68 **Tutorial** 69 70 Tutorial is loading... 71 72 **Solution (Roms)** 73 74 ``` 75 #include <bits/stdc++.h> 76 77 using namespace std; 78 79 const int N = int(3e5) + 99; 80 81 int n, m; 82 int l[N], r[N], s[N]; 83 int d[N]; 84 int dx[N]; 85 int res[N]; 86 int nxt[N]; 87 88 int main() { 89 scanf("%d %d", &n, &m); 90 for(int i = 0; i < m; ++i){ 91 scanf("%d %d %d", s + i, l + i, r + i); 92 --l[i], --r[i]; 93 if(s[i] == 1) 94 ++d[l[i]], --d[r[i]]; 95 } 96 97 memset(dx, -1, sizeof dx); 98 int sum = 0; 99 for(int i = 0; i < n - 1; ++i){ 100 sum += d[i]; 101 if(sum > 0) 102 dx[i] = 0; 103 } 104 105 res[0] = n; 106 for(int i = 1; i < n; ++i) 107 res[i] = res[i - 1] + dx[i - 1]; 108 109 nxt[n - 1] = n - 1; 110 for(int i = n - 2; i >= 0; --i){ 111 if(res[i] <= res[i + 1]) 112 nxt[i] = nxt[i + 1]; 113 else 114 nxt[i] = i; 115 } 116 117 for(int i = 0; i < m; ++i){ 118 if(s[i] != (nxt[l[i]] >= r[i])){ 119 puts("NO"); 120 return 0; 121 } 122 } 123 124 puts("YES"); 125 for(int i = 0; i < n; ++i) 126 printf("%d ", res[i]); 127 puts(""); 128 129 return 0; 130 } 131 ``` 132 133 [1187D - Subarray Sorting](/contest/1187/problem/D "Educational Codeforces Round 67 (Rated for Div. 2)") 134 135 Idea: [Roms](/profile/Roms "Master Roms") 136 137 **Tutorial** 138 139 Tutorial is loading... 140 141 **Solution (Roms)** 142 143 ``` 144 #include <bits/stdc++.h> 145 146 using namespace std; 147 148 const int N = int(3e5) + 99; 149 const int INF = int(1e9) + 99; 150 151 int t, n; 152 int a[N], b[N]; 153 vector <int> p[N]; 154 int st[4 * N + 55]; 155 156 int getMin(int v, int l, int r, int L, int R){ 157 if(L >= R) return INF; 158 if(l == L && r == R) 159 return st[v]; 160 161 int mid = (l + r) / 2; 162 return min(getMin(v * 2 + 1, l, mid, L, min(R, mid)), 163 getMin(v * 2 + 2, mid, r, max(mid, L), R)); 164 } 165 166 void upd(int v, int l, int r, int pos, int x){ 167 if(r - l == 1){ 168 st[v] = x; 169 return; 170 } 171 172 int mid = (l + r) / 2; 173 if(pos < mid) upd(v * 2 + 1, l, mid, pos, x); 174 else upd(v * 2 + 2, mid, r, pos, x); 175 176 st[v] = min(st[v * 2 + 1], st[v * 2 + 2]); 177 } 178 179 int main() { 180 scanf("%d", &t); 181 for(int tc = 0; tc < t; ++tc){ 182 scanf("%d", &n); 183 for(int i = 0; i < n; ++i) 184 p[i].clear(); 185 for(int i = 0; i < n; ++i){ 186 scanf("%d", a + i); 187 --a[i]; 188 p[a[i]].push_back(i); 189 } 190 for(int i = 0; i < n; ++i){ 191 scanf("%d", b + i); 192 --b[i]; 193 } 194 195 for(int i = 0; i < 4 * n; ++i) st[i] = INF; 196 for(int i = 0; i < n; ++i){ 197 reverse(p[i].begin(), p[i].end()); 198 if(!p[i].empty()) upd(0, 0, n, i, p[i].back()); 199 } 200 201 bool ok = true; 202 for(int i = 0; i < n; ++i){ 203 if(p[b[i]].empty()){ 204 ok = false; 205 break; 206 } 207 208 int pos = p[b[i]].back(); 209 if(getMin(0, 0, n, 0, b[i]) < pos){ 210 ok = false; 211 break; 212 } 213 214 p[b[i]].pop_back(); 215 upd(0, 0, n, b[i], p[b[i]].empty()? INF : p[b[i]].back()); 216 } 217 218 if(ok) puts("YES"); 219 else puts("NO"); 220 } 221 222 return 0; 223 } 224 ``` 225 226 [1187E - Tree Painting](/contest/1187/problem/E "Educational Codeforces Round 67 (Rated for Div. 2)") 227 228 Idea: [BledDest](/profile/BledDest "Grandmaster BledDest") 229 230 **Tutorial** 231 232 Tutorial is loading... 233 234 **Solution (Vovuh)** 235 236 ``` 237 #include <bits/stdc++.h> 238 239 using namespace std; 240 241 int n; 242 long long ans; 243 vector<int> siz; 244 vector<long long> dp; 245 vector<vector<int>> g; 246 247 int calcsize(int v, int p = -1) { 248 siz[v] = 1; 249 for (auto to : g[v]) { 250 if (to == p) continue; 251 siz[v] += calcsize(to, v); 252 } 253 return siz[v]; 254 } 255 256 long long calcdp(int v, int p = -1) { 257 dp[v] = siz[v]; 258 for (auto to : g[v]) { 259 if (to == p) continue; 260 dp[v] += calcdp(to, v); 261 } 262 return dp[v]; 263 } 264 265 void dfs(int v, int p = -1) { 266 ans = max(ans, dp[v]); 267 for (auto to : g[v]) { 268 if (to == p) continue; 269 270 dp[v] -= dp[to]; 271 dp[v] -= siz[to]; 272 siz[v] -= siz[to]; 273 siz[to] += siz[v]; 274 dp[to] += siz[v]; 275 dp[to] += dp[v]; 276 277 dfs(to, v); 278 279 dp[to] -= dp[v]; 280 dp[to] -= siz[v]; 281 siz[to] -= siz[v]; 282 siz[v] += siz[to]; 283 dp[v] += siz[to]; 284 dp[v] += dp[to]; 285 } 286 } 287 288 int main() { 289 #ifdef _DEBUG 290 freopen("input.txt", "r", stdin); 291 // freopen("output.txt", "w", stdout); 292 #endif 293 294 cin >> n; 295 g = vector<vector<int>>(n); 296 for (int i = 0; i < n - 1; ++i) { 297 int x, y; 298 cin >> x >> y; 299 --x, --y; 300 g[x].push_back(y); 301 g[y].push_back(x); 302 } 303 304 ans = 0; 305 siz = vector<int>(n); 306 dp = vector<long long>(n); 307 308 calcsize(0); 309 calcdp(0); 310 dfs(0); 311 312 cout << ans << endl; 313 314 return 0; 315 } 316 ``` 317 318 **Alternative solution (PikMike)** 319 320 ``` 321 #include <bits/stdc++.h> 322 323 #define forn(i, n) for (int i = 0; i < int(n); i++) 324 325 typedef long long li; 326 327 using namespace std; 328 329 const int N = 200 * 1000 + 13; 330 331 int n; 332 vector<int> g[N]; 333 334 int siz[N]; 335 li sum[N]; 336 337 void init(int v, int p = -1){ 338 siz[v] = 1; 339 sum[v] = 0; 340 for (auto u : g[v]) if (u != p){ 341 init(u, v); 342 siz[v] += siz[u]; 343 sum[v] += sum[u]; 344 } 345 sum[v] += (siz[v] - 1); 346 } 347 348 li dp[N]; 349 350 void dfs(int v, int p = -1){ 351 dp[v] = 0; 352 li tot = 0; 353 for (auto u : g[v]) if (u != p) 354 tot += sum[u]; 355 for (auto u : g[v]) if (u != p){ 356 dfs(u, v); 357 dp[v] = max(dp[v], (n - siz[u] - 1) + dp[u] + (tot - sum[u])); 358 } 359 if (g[v].size() == 1){ 360 dp[v] = n - 1; 361 } 362 } 363 364 int main() { 365 scanf("%d", &n); 366 forn(i, n - 1){ 367 int v, u; 368 scanf("%d%d", &v, &u); 369 --v, --u; 370 g[v].push_back(u); 371 g[u].push_back(v); 372 } 373 374 if (n == 2) { 375 cout << 3 << endl; 376 return 0; 377 } 378 379 forn(i, n) if (int(g[i].size()) > 1){ 380 init(i); 381 dfs(i); 382 printf("%lld\n", dp[i] + n); 383 break; 384 } 385 386 return 0; 387 } 388 ``` 389 390 [1187F - Expected Square Beauty](/contest/1187/problem/F "Educational Codeforces Round 67 (Rated for Div. 2)") 391 392 Idea: [Roms](/profile/Roms "Master Roms") and [adedalic](/profile/adedalic "International Master adedalic") 393 394 **Tutorial** 395 396 Tutorial is loading... 397 398 **Solution (adedalic)** 399 400 ``` 401 #include<bits/stdc++.h> 402 403 using namespace std; 404 405 #define fore(i, l, r) for(int i = int(l); i < int(r); i++) 406 #define sz(a) int((a).size()) 407 408 #define x first 409 #define y second 410 411 typedef long long li; 412 typedef pair<int, int> pt; 413 414 const int MOD = int(1e9) + 7; 415 416 int norm(int a) { 417 while(a >= MOD) a -= MOD; 418 while(a < 0) a += MOD; 419 return a; 420 } 421 int mul(int a, int b) { 422 return int(a * 1ll * b % MOD); 423 } 424 int binPow(int a, int k) { 425 int ans = 1; 426 for(; k > 0; k >>= 1) { 427 if(k & 1) 428 ans = mul(ans, a); 429 a = mul(a, a); 430 } 431 return ans; 432 } 433 int inv(int a) { 434 int b = binPow(a, MOD - 2); 435 assert(mul(a, b) == 1); 436 return b; 437 } 438 439 int n; 440 vector<int> l, r; 441 442 inline bool read() { 443 if(!(cin >> n)) 444 return false; 445 l.resize(n); 446 r.resize(n); 447 448 fore(i, 0, n) 449 cin >> l[i]; 450 fore(i, 0, n) { 451 cin >> r[i]; 452 r[i]++; 453 } 454 return true; 455 } 456 457 vector<int> p; 458 459 int calcEq(int i0) { 460 int i1 = i0 + 1; 461 int pSame = 0; 462 if(i0 > 0) { 463 int cnt = max(0, min({r[i0 - 1], r[i0], r[i1]}) - max({l[i0 - 1], l[i0], l[i1]})); 464 pSame = mul(cnt, inv(mul(mul(r[i0 - 1] - l[i0 - 1], r[i0] - l[i0]), r[i1] - l[i1]))); 465 } 466 return norm(1 - norm(2 - p[i0] - p[i1]) + pSame); 467 } 468 469 inline void solve() { 470 p.assign(n, 0); 471 p[0] = 1; 472 fore(i, 1, n) { 473 int cnt = max(0, min(r[i - 1], r[i]) - max(l[i - 1], l[i])); 474 p[i] = norm(1 - mul(cnt, inv(mul(r[i - 1] - l[i - 1], r[i] - l[i])))); 475 } 476 477 int sum = 0; 478 fore(i, 0, n) 479 sum = norm(sum + p[i]); 480 481 int ans = 0; 482 fore(i, 0, n) { 483 int curS = sum; 484 for(int j = max(0, i - 1); j < min(n, i + 2); j++) 485 curS = norm(curS - p[j]); 486 487 ans = norm(ans + mul(p[i], curS)); 488 489 if(i > 0) 490 ans = norm(ans + calcEq(i - 1)); 491 ans = norm(ans + p[i]); 492 if(i + 1 < n) 493 ans = norm(ans + calcEq(i)); 494 } 495 496 cout << ans << endl; 497 } 498 499 int main() { 500 #ifdef _DEBUG 501 freopen("input.txt", "r", stdin); 502 int tt = clock(); 503 #endif 504 ios_base::sync_with_stdio(false); 505 cin.tie(0), cout.tie(0); 506 cout << fixed << setprecision(15); 507 508 if(read()) { 509 solve(); 510 511 #ifdef _DEBUG 512 cerr << "TIME = " << clock() - tt << endl; 513 tt = clock(); 514 #endif 515 } 516 return 0; 517 } 518 ``` 519 520 [1187G - Gang Up](/contest/1187/problem/G "Educational Codeforces Round 67 (Rated for Div. 2)") 521 522 Idea: [BledDest](/profile/BledDest "Grandmaster BledDest") 523 524 **Tutorial** 525 526 Tutorial is loading... 527 528 **Solution (BledDest)** 529 530 ``` 531 #include<bits/stdc++.h> 532 533 using namespace std; 534 535 struct edge 536 { 537 int y, c, f, cost; 538 edge() {}; 539 edge(int y, int c, int f, int cost) : y(y), c(c), f(f), cost(cost) {}; 540 }; 541 542 vector<edge> e; 543 544 const int N = 14043; 545 vector<int> g[N]; 546 547 long long ans = 0; 548 long long d[N]; 549 int p[N]; 550 int pe[N]; 551 int inq[N]; 552 553 const long long INF64 = (long long)(1e18); 554 555 int s = N - 2; 556 int t = N - 1; 557 558 int rem(int x) 559 { 560 return e[x].c - e[x].f; 561 } 562 563 void push_flow() 564 { 565 for(int i = 0; i < N; i++) d[i] = INF64, p[i] = -1, pe[i] = -1, inq[i] = 0; 566 d[s] = 0; 567 queue<int> q; 568 q.push(s); 569 inq[s] = 1; 570 while(!q.empty()) 571 { 572 int k = q.front(); 573 q.pop(); 574 inq[k] = 0; 575 for(auto x : g[k]) 576 { 577 if(!rem(x)) continue; 578 int c = e[x].cost; 579 int y = e[x].y; 580 if(d[y] > d[k] + c) 581 { 582 d[y] = d[k] + c; 583 p[y] = k; 584 pe[y] = x; 585 if(inq[y] == 0) 586 { 587 inq[y] = 1; 588 q.push(y); 589 } 590 } 591 } 592 } 593 int cur = t; 594 // vector<int> zz(1, cur); 595 while(cur != s) 596 { 597 e[pe[cur]].f++; 598 e[pe[cur] ^ 1].f--; 599 cur = p[cur]; 600 // zz.push_back(cur); 601 } 602 // reverse(zz.begin(), zz.end()); 603 // for(auto x : zz) cerr << x << " "; 604 // cerr << endl; 605 ans += d[t]; 606 } 607 608 void add_edge(int x, int y, int c, int cost) 609 { 610 g[x].push_back(e.size()); 611 e.push_back(edge(y, c, 0, cost)); 612 g[y].push_back(e.size()); 613 e.push_back(edge(x, 0, 0, -cost)); 614 } 615 616 int main() 617 { 618 int n, m, k, c, d; 619 cin >> n >> m >> k >> c >> d; 620 for(int i = 0; i < k; i++) 621 { 622 int x; 623 cin >> x; 624 --x; 625 add_edge(s, x, 1, 0); 626 } 627 int tt = 101; 628 for(int i = 0; i < tt; i++) 629 add_edge(0 + i * n, t, k, i * c); 630 for(int i = 0; i < m; i++) 631 { 632 int x, y; 633 cin >> x >> y; 634 --x; 635 --y; 636 for(int i = 0; i < tt - 1; i++) 637 for(int j = 0; j < k; j++) 638 add_edge(x + i * n, y + i * n + n, 1, d * (j * 2 + 1)); 639 for(int i = 0; i < tt - 1; i++) 640 for(int j = 0; j < k; j++) 641 add_edge(y + i * n, x + i * n + n, 1, d * (j * 2 + 1)); 642 } 643 for(int i = 0; i < n; i++) 644 for(int j = 0; j < tt - 1; j++) 645 add_edge(i + j * n, i + j * n + n, k, 0); 646 for(int i = 0; i < k; i++) 647 push_flow(); 648 cout << ans << endl; 649 } 650 ```