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