1042.md (9367B)
1 Source: https://codeforces.com/blog/entry/61891 2 3 [1042A - Benches](/contest/1042/problem/A "Codeforces Round 510 (Div. 2)") 4 5 **Tutorial** 6 7 Tutorial is loading... 8 9 **Solution** 10 11 ``` 12 #include <set> 13 #include <algorithm> 14 #include <iostream> 15 #include <vector> 16 #include <string> 17 #include <cassert> 18 19 using namespace std; 20 21 const int N = 100 + 13; 22 23 int n, m; 24 int a[N]; 25 26 int main() { 27 cin >> n >> m; 28 for (int i = 0; i < n; i++) { 29 cin >> a[i]; 30 } 31 int ans2 = *max_element(a, a + n) + m; 32 for (int it = 0; it < m; it++) { 33 int pos = -1; 34 for (int i = 0; i < n; i++) { 35 if (pos == -1 || a[i] < a[pos]) { 36 pos = i; 37 } 38 } 39 assert(pos != -1); 40 a[pos]++; 41 } 42 int ans1 = *max_element(a, a + n); 43 cout << ans1 << ' ' << ans2 << endl; 44 } 45 ``` 46 47 [1042B - Vitamins](/contest/1042/problem/B "Codeforces Round 510 (Div. 2)") 48 49 **Tutorial** 50 51 Tutorial is loading... 52 53 **Solution** 54 55 ``` 56 #include <bits/stdc++.h> 57 58 using namespace std; 59 60 const int INF = 1e9; 61 62 int n; 63 map<string, int> was; 64 65 inline void read() { 66 cin >> n; 67 for (int i = 0; i < n; i++) { 68 int c; 69 string s; 70 cin >> c >> s; 71 sort(s.begin(), s.end()); 72 if (was.count(s) == 0) { 73 was[s] = c; 74 } else { 75 was[s] = min(was[s], c); 76 } 77 } 78 } 79 80 inline int getC(string a, string b) { 81 if (!was.count(a) || !was.count(b)) { 82 return INF; 83 } 84 return was[a] + was[b]; 85 } 86 87 inline void solve() { 88 int ans = INF; 89 if (was.count("A") && was.count("B") && was.count("C")) { 90 ans = was["A"] + was["B"] + was["C"]; 91 } 92 if (was.count("ABC")) { 93 ans = min(ans, was["ABC"]); 94 } 95 ans = min(ans, getC("AB", "C")); 96 ans = min(ans, getC("A", "BC")); 97 ans = min(ans, getC("AC", "B")); 98 ans = min(ans, getC("AB", "BC")); 99 ans = min(ans, getC("AC", "BC")); 100 ans = min(ans, getC("AC", "AB")); 101 if (ans == INF) { 102 ans = -1; 103 } 104 cout << ans << endl; 105 } 106 107 int main () { 108 read(); 109 solve(); 110 } 111 ``` 112 113 [1042C - Array Product](/contest/1042/problem/C "Codeforces Round 510 (Div. 2)") 114 115 **Tutorial** 116 117 Tutorial is loading... 118 119 **Solution** 120 121 ``` 122 #include <bits/stdc++.h> 123 124 using namespace std; 125 126 int main() { 127 #ifdef _DEBUG 128 freopen("input.txt", "r", stdin); 129 // freopen("output.txt", "w", stdout); 130 #endif 131 132 int n; 133 scanf("%d", &n); 134 vector<int> a(n); 135 for (int i = 0; i < n; ++i) 136 scanf("%d", &a[i]); 137 138 int cntneg = 0; 139 int cntzero = 0; 140 vector<int> used(n); 141 int pos = -1; 142 for (int i = 0; i < n; ++i) { 143 if (a[i] == 0) { 144 used[i] = 1; 145 ++cntzero; 146 } 147 if (a[i] < 0) { 148 ++cntneg; 149 if (pos == -1 || abs(a[pos]) > abs(a[i])) 150 pos = i; 151 } 152 } 153 if (cntneg & 1) 154 used[pos] = 1; 155 156 if (cntzero == n || (cntzero == n - 1 && cntneg == 1)) { 157 for (int i = 0; i < n - 1; ++i) 158 printf("1 %d %d\n", i + 1, i + 2); 159 return 0; 160 } 161 162 int lst = -1; 163 for (int i = 0; i < n; ++i) { 164 if (used[i]) { 165 if (lst != -1) printf("1 %d %d\n", lst + 1, i + 1); 166 lst = i; 167 } 168 } 169 if (lst != -1) printf("2 %d\n", lst + 1); 170 171 lst = -1; 172 for (int i = 0; i < n; ++i) { 173 if (!used[i]) { 174 if (lst != -1) printf("1 %d %d\n", lst + 1, i + 1); 175 lst = i; 176 } 177 } 178 179 return 0; 180 } 181 ``` 182 183 [1042D - Petya and Array](/contest/1042/problem/D "Codeforces Round 510 (Div. 2)") 184 185 **Tutorial** 186 187 Tutorial is loading... 188 189 **Solution** 190 191 ``` 192 #include <bits/stdc++.h> 193 194 #define forn(i, n) for (int i = 0; i < int(n); i++) 195 196 using namespace std; 197 198 const int N = 200 * 1000 + 13; 199 200 int n; 201 long long T; 202 int a[N]; 203 int f[N]; 204 205 void upd(int x){ 206 for (int i = x; i < N; i |= i + 1) 207 ++f[i]; 208 } 209 210 int get(int x){ 211 int res = 0; 212 for (int i = x; i >= 0; i = (i & (i + 1)) - 1) 213 res += f[i]; 214 return res; 215 } 216 217 int main() { 218 scanf("%d%lld", &n, &T); 219 forn(i, n) 220 scanf("%d", &a[i]); 221 222 vector<long long> sums(1, 0ll); 223 long long pr = 0; 224 forn(i, n){ 225 pr += a[i]; 226 sums.push_back(pr); 227 } 228 229 sort(sums.begin(), sums.end()); 230 sums.resize(unique(sums.begin(), sums.end()) - sums.begin()); 231 232 long long ans = 0; 233 pr = 0; 234 upd(lower_bound(sums.begin(), sums.end(), 0ll) - sums.begin()); 235 236 forn(i, n){ 237 pr += a[i]; 238 239 int npos = upper_bound(sums.begin(), sums.end(), pr - T) - sums.begin(); 240 ans += (i + 1 - get(npos - 1)); 241 242 int k = lower_bound(sums.begin(), sums.end(), pr) - sums.begin(); 243 upd(k); 244 } 245 246 printf("%lld\n", ans); 247 return 0; 248 } 249 ``` 250 251 [1042E - Vasya and Magic Matrix](/contest/1042/problem/E "Codeforces Round 510 (Div. 2)") 252 253 **Tutorial** 254 255 Tutorial is loading... 256 257 **Solution** 258 259 ``` 260 #include<bits/stdc++.h> 261 262 using namespace std; 263 264 const int MOD = 998244353; 265 const int N = 1009; 266 267 int mul(int a, int b){ 268 return int(a * 1LL * b % MOD); 269 } 270 271 void upd(int &a, int b){ 272 a += b; 273 while(a >= MOD) a -= MOD; 274 while(a < 0) a += MOD; 275 } 276 277 int bp(int a, int n){ 278 int res = 1; 279 for(; n > 0; n >>= 1){ 280 if(n & 1) res = mul(res, a); 281 a = mul(a, a); 282 } 283 284 return res; 285 } 286 287 int inv(int a){ 288 int ia = bp(a, MOD - 2); 289 assert(mul(a, ia) == 1); 290 return ia; 291 } 292 293 int n, m; 294 int a[N][N]; 295 int dp[N][N]; 296 int si, sj; 297 298 int main() { 299 //freopen("input.txt", "r", stdin); 300 scanf("%d %d", &n, &m); 301 for(int i = 0; i < n; ++i) 302 for(int j = 0; j < m; ++j) 303 scanf("%d", &a[i][j]); 304 scanf("%d %d", &si, &sj); 305 --si, --sj; 306 307 vector <pair<int, pair<int, int> > > v; 308 for(int i = 0; i < n; ++i) 309 for(int j = 0; j < m; ++j) 310 v.push_back(make_pair(a[i][j], make_pair(i, j))); 311 312 sort(v.begin(), v.end()); 313 int l = 0; 314 int sumDP = 0, sumX = 0, sumY = 0, sumX2 = 0, sumY2 = 0; 315 while(l < int(v.size())){ 316 int r = l; 317 while(r < int(v.size()) && v[r].first == v[l].first) ++r; 318 319 int il = -1; 320 if(l != 0) il = inv(l); 321 for(int i = l; i < r; ++i){ 322 int x = v[i].second.first, y = v[i].second.second; 323 if(il == -1){ 324 dp[x][y] = 0; 325 continue; 326 } 327 328 329 upd(dp[x][y], mul(sumDP, il)); 330 331 upd(dp[x][y], mul(x, x)); 332 upd(dp[x][y], mul(y, y)); 333 334 upd(dp[x][y], mul(sumX2, il)); 335 upd(dp[x][y], mul(sumY2, il)); 336 337 upd(dp[x][y], mul(mul(-x - x, sumX), il)); 338 upd(dp[x][y], mul(mul(-y - y, sumY), il)); 339 } 340 341 for(int i = l; i < r; ++i){ 342 int x = v[i].second.first, y = v[i].second.second; 343 344 upd(sumDP, dp[x][y]); 345 346 upd(sumX2, mul(x, x)); 347 upd(sumY2, mul(y, y)); 348 349 upd(sumX, x); 350 upd(sumY, y); 351 } 352 353 l = r; 354 355 } 356 357 printf("%d\n", dp[si][sj]); 358 return 0; 359 } 360 ``` 361 362 [1042F - Leaf Sets](/contest/1042/problem/F "Codeforces Round 510 (Div. 2)") 363 364 **Tutorial** 365 366 Tutorial is loading... 367 368 **Solution (O(n log n))** 369 370 ``` 371 #include <bits/stdc++.h> 372 373 using namespace std; 374 375 #define forn(i, n) for (int i = 0; i < int(n); ++i) 376 #define sz(a) int((a).size()) 377 378 const int N = 1000 * 1000 + 13; 379 380 int n, k; 381 vector<int> g[N]; 382 int ans; 383 384 int dfs(int v, int p = -1){ 385 if (g[v].size() == 1) 386 return 0; 387 388 vector<int> cur; 389 for (auto u : g[v]){ 390 if (u == p) continue; 391 cur.push_back(dfs(u, v) + 1); 392 } 393 sort(cur.begin(), cur.end()); 394 395 while (sz(cur) >= 2){ 396 if (cur.back() + cur[sz(cur) - 2] <= k) 397 break; 398 ++ans; 399 cur.pop_back(); 400 } 401 402 return cur.back(); 403 } 404 405 int main(){ 406 scanf("%d%d", &n, &k); 407 forn(i, n - 1){ 408 int v, u; 409 scanf("%d%d", &v, &u); 410 --v, --u; 411 g[v].push_back(u); 412 g[u].push_back(v); 413 } 414 415 forn(i, n){ 416 if (sz(g[i]) > 1){ 417 dfs(i); 418 break; 419 } 420 } 421 422 printf("%d\n", ans + 1); 423 return 0; 424 } 425 ``` 426 427 **Solution (Small to Large, O(n log^2 n))** 428 429 ``` 430 #include <bits/stdc++.h> 431 432 using namespace std; 433 434 #define forn(i, n) for (int i = 0; i < int(n); ++i) 435 #define sz(a) int((a).size()) 436 437 const int N = 1000 * 1000 + 13; 438 439 int n, k; 440 vector<int> g[N]; 441 multiset<int> val[N]; 442 int ans; 443 444 void dfs(int v, int d, int p){ 445 if (g[v].size() == 1){ 446 val[v].insert(d); 447 return; 448 } 449 450 int bst = -1; 451 for (auto u : g[v]){ 452 if (u == p) continue; 453 dfs(u, d + 1, v); 454 if (bst == -1 || sz(val[u]) > sz(val[bst])) 455 bst = u; 456 } 457 swap(val[bst], val[v]); 458 459 for (auto u : g[v]){ 460 if (u == p || u == bst) continue; 461 for (auto it : val[u]){ 462 int dd = k + 2 * d - it; 463 auto jt = val[v].upper_bound(dd); 464 if (jt == val[v].begin()){ 465 val[v].insert(it); 466 } 467 else{ 468 --jt; 469 int t = *jt; 470 val[v].erase(jt); 471 val[v].insert(max(it, t)); 472 } 473 } 474 } 475 } 476 477 int main(){ 478 scanf("%d%d", &n, &k); 479 forn(i, n - 1){ 480 int v, u; 481 scanf("%d%d", &v, &u); 482 --v, --u; 483 g[v].push_back(u); 484 g[u].push_back(v); 485 } 486 487 forn(i, n){ 488 if (sz(g[i]) > 1){ 489 dfs(i, 0, -1); 490 printf("%d\n", sz(val[i])); 491 break; 492 } 493 } 494 return 0; 495 } 496 ``` 497 498 **Solution (O(n))** 499 500 ``` 501 #include <bits/stdc++.h> 502 503 using namespace std; 504 505 #define forn(i, n) for (int i = 0; i < int(n); ++i) 506 #define sz(a) int((a).size()) 507 508 const int N = 1000 * 1000 + 13; 509 510 int n, k; 511 vector<int> g[N]; 512 int ans; 513 514 int dfs(int v, int p = -1){ 515 if (g[v].size() == 1) 516 return 0; 517 518 vector<int> cur; 519 for (auto u : g[v]){ 520 if (u == p) continue; 521 cur.push_back(dfs(u, v) + 1); 522 } 523 524 int pos = -1; 525 forn(i, sz(cur)) { 526 if (cur[i] * 2 <= k && (pos == -1 || cur[pos] < cur[i])) 527 pos = i; 528 } 529 530 if (pos == -1) { 531 ans += sz(cur) - 1; 532 return *min_element(cur.begin(), cur.end()); 533 } 534 535 int res = -1; 536 forn(i, sz(cur)) { 537 if (cur[pos] >= cur[i]) continue; 538 if (cur[i] + cur[pos] <= k && (res == -1 || cur[i] < cur[res])) 539 res = i; 540 } 541 542 forn(i, sz(cur)) 543 ans += (cur[i] > cur[pos]); 544 if (res != -1) 545 --ans; 546 547 return (res == -1 ? cur[pos] : cur[res]); 548 } 549 550 int main(){ 551 scanf("%d%d", &n, &k); 552 forn(i, n - 1) { 553 int v, u; 554 scanf("%d%d", &v, &u); 555 --v, --u; 556 g[v].push_back(u); 557 g[u].push_back(v); 558 } 559 560 forn(i, n) { 561 if (sz(g[i]) > 1) { 562 dfs(i); 563 break; 564 } 565 } 566 567 printf("%d\n", ans + 1); 568 return 0; 569 } 570 ```