1702.md (10360B)
1 Source: https://codeforces.com/blog/entry/104763 2 3 [1702A - Round Down the Price](/contest/1702/problem/A "Codeforces Round 805 (Div. 3)") 4 5 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 6 7 **Tutorial** 8 9 Tutorial is loading... 10 11 **Solution** 12 13 ``` 14 #include <bits/stdc++.h> 15 16 using namespace std; 17 18 #define forn(i, n) for (int i = 0; i < int(n); i++) 19 #define sz(v) (int)v.size() 20 #define all(v) v.begin(),v.end() 21 #define eb emplace_back 22 23 void solve() { 24 int m; cin >> m; 25 string t = to_string(m); 26 string s = "1"; 27 for (int i = 1; i < sz(t); i++) { 28 s += '0'; 29 } 30 int k = stoi(s); 31 cout << m - k << '\n'; 32 } 33 34 int main() { 35 int t; 36 cin >> t; 37 38 forn(tt, t) { 39 solve(); 40 } 41 } 42 ``` 43 44 [1702B - Polycarp Writes a String from Memory](/contest/1702/problem/B "Codeforces Round 805 (Div. 3)") 45 46 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 47 48 **Tutorial** 49 50 Tutorial is loading... 51 52 **Solution** 53 54 ``` 55 #include <bits/stdc++.h> 56 57 using namespace std; 58 59 #define forn(i, n) for (int i = 0; i < int(n); i++) 60 #define sz(v) (int)v.size() 61 #define all(v) v.begin(),v.end() 62 #define eb emplace_back 63 64 void solve() { 65 string s; cin >> s; 66 set<char> v; 67 int ans = 0; 68 for (int i = 0; i < sz(s); i++) { 69 v.insert(s[i]); 70 if (sz(v) > 3) { 71 ans++; 72 v.clear(); 73 v.insert(s[i]); 74 } 75 } 76 if (!v.empty()) ans++; 77 cout << ans << endl; 78 } 79 80 int main() { 81 int t; 82 cin >> t; 83 84 forn(tt, t) { 85 solve(); 86 } 87 } 88 ``` 89 90 [1702C - Train and Queries](/contest/1702/problem/C "Codeforces Round 805 (Div. 3)") 91 92 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 93 94 **Tutorial** 95 96 Tutorial is loading... 97 98 **Solution** 99 100 ``` 101 #include<bits/stdc++.h> 102 using namespace std; 103 #define forn(i, n) for (int i = 0; i < int(n); i++) 104 105 void solve(){ 106 int n, k; 107 cin >> n >> k; 108 map<int, pair<int, int>>m; 109 forn(i, n){ 110 int u; 111 cin >> u; 112 if(!m.count(u)) { 113 m[u].first = i; 114 m[u].second = i; 115 } 116 else m[u].second = i; 117 } 118 forn(i, k){ 119 int a, b; 120 cin >> a >> b; 121 if(!m.count(a) or !m.count(b) or m[a].first > m[b].second) { 122 cout << "NO\n"; //equals = 0 = wrong 123 } 124 else cout << "YES\n"; 125 } 126 } 127 128 int main(){ 129 int t; 130 cin >> t; 131 while(t--){ 132 solve(); 133 } 134 } 135 ``` 136 137 [1702D - Not a Cheap String](/contest/1702/problem/D "Codeforces Round 805 (Div. 3)") 138 139 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 140 141 **Tutorial** 142 143 Tutorial is loading... 144 145 **Solution** 146 147 ``` 148 #include <bits/stdc++.h> 149 150 using namespace std; 151 152 #define forn(i, n) for (int i = 0; i < int(n); i++) 153 154 int main() { 155 int t; 156 cin >> t; 157 forn(tt, t) { 158 string s; 159 cin >> s; 160 int p; 161 cin >> p; 162 string w(s); 163 sort(w.rbegin(), w.rend()); 164 int cost = 0; 165 forn(i, s.length()) 166 cost += s[i] - 'a' + 1; 167 map<char,int> del; 168 forn(i, w.length()) 169 if (cost > p) { 170 del[w[i]]++; 171 cost -= w[i] - 'a' + 1; 172 } 173 forn(i, s.length()) { 174 if (del[s[i]] > 0) { 175 del[s[i]]--; 176 continue; 177 } 178 cout << s[i]; 179 } 180 cout << endl; 181 } 182 } 183 ``` 184 185 [1702E - Split Into Two Sets](/contest/1702/problem/E "Codeforces Round 805 (Div. 3)") 186 187 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 188 189 **Tutorial** 190 191 Tutorial is loading... 192 193 **Solution** 194 195 ``` 196 #include <bits/stdc++.h> 197 198 using namespace std; 199 200 typedef long long ll; 201 202 #define forn(i, n) for (int i = 0; i < int(n); i++) 203 204 map<int, vector<int>> m; 205 vector<bool> used; 206 207 int go(int v) { 208 used[v] = true; 209 for (auto now : m[v]) { 210 if (!used[now]) { 211 return go(now) + 1; 212 } 213 } 214 return 1; 215 } 216 217 void solve() { 218 219 int n, x, y; 220 cin >> n; 221 222 m.clear(); 223 used.clear(); 224 used.resize(n + 1, false); 225 226 bool fault = false; 227 forn(i, n) { 228 cin >> x >> y; 229 m[x].push_back(y); 230 m[y].push_back(x); 231 if (x == y || m[x].size() > 2 || m[y].size() > 2) fault = true; 232 } 233 234 if (fault) { 235 cout << "NO\n"; 236 return; 237 } 238 239 forn(i, n) { 240 if (!used[i + 1]) { 241 if (go(i + 1) % 2) { 242 cout << "NO\n"; 243 return; 244 } 245 } 246 } 247 248 cout << "YES\n"; 249 } 250 int main() { 251 int tests; 252 cin >> tests; 253 forn(tt, tests) { 254 solve(); 255 } 256 } 257 ``` 258 259 [1702F - Equate Multisets](/contest/1702/problem/F "Codeforces Round 805 (Div. 3)") 260 261 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 262 263 **Tutorial** 264 265 Tutorial is loading... 266 267 **Solution** 268 269 ``` 270 #include <bits/stdc++.h> 271 272 using namespace std; 273 274 #define forn(i, n) for (int i = 0; i < int(n); i++) 275 #define sz(v) (int)v.size() 276 #define all(v) v.begin(),v.end() 277 #define eb emplace_back 278 279 const int INF = 1e9; 280 281 void solve() { 282 int n; cin >> n; 283 multiset<int> a, b; 284 285 forn(i, n) { 286 int x; cin >> x; 287 while (x % 2 == 0) { 288 x /= 2; 289 } 290 a.insert(x); 291 } 292 293 forn(i, n) { 294 int x; cin >> x; 295 b.insert(x); 296 } 297 n = sz(a); 298 299 while (!b.empty()) { 300 int x = *b.rbegin(); 301 // cout << x << endl; 302 if (!a.count(x)) { 303 if (x == 1) break; 304 b.erase(b.find(x)); 305 b.insert(x / 2); 306 } else { 307 b.erase(b.find(x)); 308 a.erase(a.find(x)); 309 } 310 } 311 312 cout << (b.empty() ? "YES" : "NO") << endl; 313 314 } 315 316 int main() { 317 int t; 318 cin >> t; 319 320 forn(tt, t) { 321 solve(); 322 } 323 } 324 ``` 325 326 [1702G1 - Passable Paths (easy version)](/contest/1702/problem/G1 "Codeforces Round 805 (Div. 3)") 327 328 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 329 330 **Tutorial** 331 332 Tutorial is loading... 333 334 **Solution** 335 336 ``` 337 #include <bits/stdc++.h> 338 339 #define int long long 340 #define pb emplace_back 341 #define mp make_pair 342 #define x first 343 #define y second 344 #define all(a) a.begin(), a.end() 345 #define rall(a) a.rbegin(), a.rend() 346 347 typedef long double ld; 348 typedef long long ll; 349 350 using namespace std; 351 352 mt19937 rnd(143); 353 354 const int inf = 1e15; 355 const int M = 1e9 + 7; 356 const ld pi = atan2(0, -1); 357 const ld eps = 1e-6; 358 359 void depth(int v, int p, vector<vector<int>> &sl, vector<int> &d){ 360 if(p >= 0) d[v] = d[p] + 1; 361 for(int u: sl[v]){ 362 if(u == p) continue; 363 depth(u, v, sl, d); 364 } 365 } 366 367 int dfs(int v, int p, vector<vector<int>> &sl, vector<bool> &chosen){ 368 int res = 0; 369 bool lower = false; 370 for(int u: sl[v]){ 371 if(u == p) continue; 372 res += dfs(u, v, sl, chosen); 373 lower = lower || chosen[u]; 374 } 375 chosen[v] = chosen[v] || lower; 376 if(chosen[v] && !lower) res = 1; 377 return res; 378 } 379 380 void solve(){ 381 int n; 382 cin >> n; 383 vector<vector<int>> sl(n); 384 for(int i = 1; i < n; ++i){ 385 int u, v; 386 cin >> u >> v; 387 sl[--u].push_back(--v); 388 sl[v].push_back(u); 389 } 390 vector<int> d(n); 391 depth(0, -1, sl, d); 392 int q; 393 cin >> q; 394 for(; q; --q){ 395 int k; 396 cin >> k; 397 vector<bool> chosen(n); 398 int mx = 0; 399 for(int i = 0; i < k; ++i){ 400 int p; 401 cin >> p; 402 --p; 403 if(d[p] > d[mx]) mx = p; 404 chosen[p] = true; 405 } 406 int leaves = dfs(mx, -1, sl, chosen); 407 if(leaves == 1) cout << "YES\n"; 408 else cout << "NO\n"; 409 } 410 } 411 412 bool multi = false; 413 414 signed main() { 415 int t = 1; 416 if (multi)cin >> t; 417 for (; t; --t) { 418 solve(); 419 //cout << endl; 420 } 421 return 0; 422 } 423 ``` 424 425 [1702G2 - Passable Paths (hard version)](/contest/1702/problem/G2 "Codeforces Round 805 (Div. 3)") 426 427 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 428 429 **Tutorial** 430 431 Tutorial is loading... 432 433 **Solution** 434 435 ``` 436 #include <bits/stdc++.h> 437 438 #define int long long 439 #define pb emplace_back 440 #define mp make_pair 441 #define x first 442 #define y second 443 #define all(a) a.begin(), a.end() 444 #define rall(a) a.rbegin(), a.rend() 445 446 typedef long double ld; 447 typedef long long ll; 448 449 using namespace std; 450 451 mt19937 rnd(143); 452 453 const int inf = 1e15; 454 const int M = 1e9 + 7; 455 const ld pi = atan2(0, -1); 456 const ld eps = 1e-6; 457 458 int n, sz; 459 vector<vector<int>> sl, up; 460 vector<int> d; 461 462 void precalc(int v, int p){ 463 d[v] = d[p] + 1; 464 up[v][0] = p; 465 for(int i = 1; i <= sz; ++i){ 466 up[v][i] = up[up[v][i - 1]][i - 1]; 467 } 468 for(int u: sl[v]){ 469 if(u == p) continue; 470 precalc(u, v); 471 } 472 } 473 474 int lca(int u, int v){ 475 if(d[u] < d[v]){ 476 swap(u, v); 477 } 478 for(int cur = sz; cur >= 0; --cur){ 479 if (d[u] - (1 << cur) >= d[v]) { 480 u = up[u][cur]; 481 } 482 } 483 for(int cur = sz; cur >= 0; --cur){ 484 if (up[u][cur] != up[v][cur]) { 485 u = up[u][cur]; 486 v = up[v][cur]; 487 } 488 } 489 return u == v ? u : up[u][0]; 490 } 491 492 void solve(){ 493 cin >> n; 494 sz = 0; 495 while ((1 << sz) < n) sz++; 496 d.assign(n, -1); 497 up.assign(n, vector<int>(sz + 1)); 498 sl.assign(n, vector<int>(0)); 499 for(int i = 1; i < n; ++i){ 500 int u, v; 501 cin >> u >> v; 502 sl[--u].push_back(--v); 503 sl[v].push_back(u); 504 } 505 precalc(0, 0); 506 int q; 507 cin >> q; 508 for(; q; --q){ 509 int k; 510 cin >> k; 511 vector<int> p(k); 512 for(int &e: p) { 513 cin >> e; 514 --e; 515 } 516 sort(all(p), [](int a, int b) { 517 return d[a] > d[b]; 518 }); 519 vector<bool> used(k); 520 for(int i = 0; i < k; ++i){ 521 if(lca(p[0], p[i]) == p[i]) used[i] = true; 522 } 523 int f = 0; 524 while (f < k && used[f]) f++; 525 if(f == k){ 526 cout << "YES\n"; 527 continue; 528 } 529 bool ans = true; 530 for(int i = f; i < k; ++i){ 531 if(lca(p[f], p[i]) == p[i]) used[i] = true; 532 } 533 for(bool e: used){ 534 ans &= e; 535 } 536 ans &= d[lca(p[0], p[f])] <= d[p.back()]; 537 if(ans) cout << "YES\n"; 538 else cout << "NO\n"; 539 } 540 } 541 542 bool multi = false; 543 544 signed main() { 545 int t = 1; 546 if (multi)cin >> t; 547 for (; t; --t) { 548 solve(); 549 //cout << endl; 550 } 551 return 0; 552 } 553 ```