1388.md (11173B)
1 Source: https://codeforces.com/blog/entry/80828 2 3 [1388A - Captain Flint and Crew Recruitment](/contest/1388/problem/A "Codeforces Round 660 (Div. 2)") 4 5 Idea: [Denisov](/profile/Denisov "Master Denisov") 6 7 **Tutorial** 8 9 Tutorial is loading... 10 11 **Solution (Karavaev1101)** 12 13 ``` 14 #include <bits/stdc++.h> 15 16 using namespace std; 17 18 int main(){ 19 ios_base::sync_with_stdio(false); 20 cin.tie(nullptr); cout.tie(nullptr); 21 22 int q; 23 cin >> q; 24 25 while(q--){ 26 int n; cin >> n; 27 if(n <= 30){ 28 cout << "NO" << endl; 29 } 30 else{ 31 cout << "YES" << endl; 32 if(n == 36 || n == 40 || n == 44){ 33 cout << 6 << ' ' << 10 << ' ' << 15 << ' ' << n - 31 << endl; 34 } 35 else{ 36 cout << 6 << ' ' << 10 << ' ' << 14 << ' ' << n - 30 << endl; 37 } 38 } 39 } 40 } 41 ``` 42 43 [1388B - Captain Flint and a Long Voyage](/contest/1388/problem/B "Codeforces Round 660 (Div. 2)") 44 45 Idea: [karavaiev](/profile/karavaiev "Candidate Master karavaiev") 46 47 **Tutorial** 48 49 Tutorial is loading... 50 51 **Solution (Karavaev1101)** 52 53 ``` 54 #include <bits/stdc++.h> 55 56 using namespace std; 57 58 int main() { 59 ios_base::sync_with_stdio(false); 60 cin.tie(nullptr); cout.tie(nullptr); 61 62 int q; 63 cin >> q; 64 65 while (q--) { 66 int n; cin >> n; 67 int x = (n + 3) / 4; 68 for (int i = 0; i < n - x; ++i) { 69 cout << 9; 70 } 71 for (int i = 0; i < x; ++i) { 72 cout << 8; 73 } 74 cout << endl; 75 } 76 } 77 ``` 78 79 [1388C - Uncle Bogdan and Country Happiness](/contest/1388/problem/C "Codeforces Round 660 (Div. 2)") 80 81 Idea: [karavaiev](/profile/karavaiev "Candidate Master karavaiev") 82 83 **Tutorial** 84 85 Tutorial is loading... 86 87 **Solution (Karavaev1101)** 88 89 ``` 90 #include <bits/stdc++.h> 91 92 using namespace std; 93 94 const int N = 1e5 + 7; 95 96 vector < int > gr[N]; 97 98 bool access = true; 99 100 int p[N], h[N], a[N], g[N]; 101 102 void dfs(int v, int ancestor = -1) { 103 a[v] = p[v]; 104 int sum_g = 0; 105 for (int to : gr[v]) { 106 if (to == ancestor) continue; 107 dfs(to, v); 108 sum_g += g[to]; 109 a[v] += a[to]; 110 } 111 if ((a[v] + h[v]) % 2 == 0) {} // first 112 else access = false; 113 g[v] = (a[v] + h[v]) / 2; 114 if (g[v] >= 0 && g[v] <= a[v]) {} // second 115 else access = false; 116 if (sum_g <= g[v]) {} // third 117 else access = false; 118 } 119 120 int main() { 121 ios_base::sync_with_stdio(false); 122 cin.tie(nullptr); cout.tie(nullptr); 123 124 int q; 125 cin >> q; 126 127 while (q--) { 128 int n, m; cin >> n >> m; 129 for (int i = 0; i < n; ++i) cin >> p[i]; 130 for (int i = 0; i < n; ++i) cin >> h[i]; 131 for (int i = 0; i < n - 1; ++i) { 132 int a, b; cin >> a >> b; 133 --a, --b; 134 gr[a].push_back(b); 135 gr[b].push_back(a); 136 } 137 dfs(0); 138 cout << (access ? "YES" : "NO") << endl; 139 access = true; 140 for (int i = 0; i < n; ++i) gr[i].clear(); 141 } 142 } 143 ``` 144 145 [1388D - Captain Flint and Treasure](/contest/1388/problem/D "Codeforces Round 660 (Div. 2)") 146 147 Idea: [Denisov](/profile/Denisov "Master Denisov") 148 149 **Tutorial** 150 151 Tutorial is loading... 152 153 **Solution (Denisov)** 154 155 ``` 156 #include <bits/stdc++.h> 157 #define ll long long 158 #define all(a) a.begin(),a.end() 159 160 using namespace std; 161 162 vector <vector <int> > edge; 163 vector <ll> a; 164 vector <int> b, used; 165 vector <int> order[2]; 166 ll ans; 167 inline void dfs (int v) { 168 used[v] = 1; 169 for (int to : edge[v]) { 170 if (!used[to]) dfs(to); 171 } 172 ans += a[v]; 173 if (b[v] != -1 && a[v] > 0) { 174 a[b[v]] += a[v]; 175 } 176 if (a[v] > 0) { 177 order[0].push_back(v); 178 } 179 else { 180 order[1].push_back(v); 181 } 182 } 183 inline void solve () { 184 for (auto &i : edge) i.clear(); 185 edge.clear(); 186 a.clear(); 187 order[0].clear(); 188 order[1].clear(); 189 b.clear(); 190 used.clear(); 191 int n, x; 192 cin >> n; 193 edge.resize(n); 194 a.resize(n); 195 b.resize(n); 196 for (auto &i : a) cin >> i; 197 for (int i = 0; i < n; i++) { 198 cin >> x; 199 if (x != -1) { 200 --x; 201 edge[x].push_back(i); 202 } 203 b[i] = x; 204 } 205 ans = 0; 206 used.assign(n, 0); 207 for (int i = 0; i < n; i++) { 208 if (!used[i]) { 209 dfs(i); 210 } 211 } 212 cout << ans << '\n'; 213 reverse(all(order[1])); 214 for (auto &i : order[0]) cout << i + 1 << ' '; 215 for (auto &i : order[1]) cout << i + 1 << ' '; 216 cout << '\n'; 217 } 218 main() 219 { 220 ios::sync_with_stdio(0); 221 ios_base::sync_with_stdio(0); 222 cin.tie(0); 223 cout.tie(0); 224 solve(); 225 } 226 ``` 227 228 **Solution (Karavaev1101)** 229 230 ``` 231 #include <bits/stdc++.h> 232 233 #define Vanya Unstoppable 234 235 using namespace std; 236 237 int main() { 238 ios_base::sync_with_stdio(false); 239 cin.tie(nullptr); cout.tie(nullptr); 240 241 int n; 242 cin >> n; 243 244 long long a[n]; 245 for (int i = 0; i < n; ++i) { 246 cin >> a[i]; 247 } 248 249 set < int > s; 250 for (int i = 0; i < n; ++i) { 251 s.insert(i); 252 } 253 254 int b[n]; 255 vector < int > sz(n); 256 for (int i = 0; i < n; ++i) { 257 cin >> b[i]; --b[i]; 258 if (b[i] == -2) continue; 259 ++sz[b[i]]; 260 if (sz[b[i]] == 1) { 261 s.erase(b[i]); 262 } 263 } 264 265 long long sum = 0; 266 vector < int > ans[2]; 267 268 while (!s.empty()) { 269 int v = *s.begin(); 270 s.erase(s.begin()); 271 int w = b[v]; 272 sum += a[v]; 273 if (a[v] >= 0) { 274 if (w >= 0) { 275 a[w] += a[v]; 276 } 277 ans[0].push_back(v); 278 } else { 279 ans[1].push_back(v); 280 } 281 if (w >= 0) { 282 --sz[w]; 283 if (sz[w] == 0) { 284 s.insert(w); 285 } 286 } 287 } 288 289 cout << sum << endl; 290 for (int to : ans[0]) cout << to + 1 << ' '; 291 292 reverse(ans[1].begin(), ans[1].end()); 293 294 for (int to : ans[1]) cout << to + 1 << ' '; 295 cout << endl; 296 } 297 ``` 298 299 [1388E - Uncle Bogdan and Projections](/contest/1388/problem/E "Codeforces Round 660 (Div. 2)") 300 301 Idea: [perekopskiy](/profile/perekopskiy "International Master perekopskiy") 302 303 **Tutorial** 304 305 Tutorial is loading... 306 307 **Solution (perekopskiy)** 308 309 ``` 310 #include <bits/stdc++.h> 311 312 #define pb push_back 313 #define x first 314 #define y second 315 316 using namespace std; 317 318 const int N = 1e5 + 10; 319 const double eps = 1e-9; 320 321 double xl[N], xr[N], y[N], pi = acos(-1), mn_x, mx_x; 322 int ind_l, ind_r; 323 324 double point_pr(double x, double y, double ctg) { 325 return x - y * ctg; 326 } 327 328 signed main() { 329 ios_base::sync_with_stdio(0); 330 cin.tie(0); 331 cout.tie(0); 332 int n; 333 vector<pair<double, int> > q; 334 vector<pair<double, pair<int, int> > > events, prom_left, prom_right; 335 cin >> n; 336 pair<double, double> mx, mn; 337 mx = {-1.0, -1.0}; 338 mn = {2e9, 2e9}; 339 mn_x = 2e9; 340 mx_x = -2e9; 341 for(int i = 0; i < n; ++i) { 342 cin >> xl[i] >> xr[i] >> y[i]; 343 344 if(xl[i] < mn_x) { 345 mn_x = xl[i]; 346 } 347 if(xr[i] > mx_x) { 348 mx_x = xr[i]; 349 } 350 351 if(mx.y < y[i]) { 352 mx.y = y[i]; 353 mx.x = xl[i]; 354 ind_l = i; 355 } 356 else if(mx.y == y[i] && mx.x > xl[i]) { 357 mx.y = y[i]; 358 mx.x = xl[i]; 359 ind_l = i; 360 } 361 362 if(mn.y > y[i]) { 363 mn.y = y[i]; 364 mn.x = xl[i]; 365 ind_r = i; 366 } 367 else if(mn.y == y[i] && mn.x < xl[i]) { 368 mn.y = y[i]; 369 mn.x = xl[i]; 370 ind_r = i; 371 } 372 } 373 double a1, a2; 374 for(int i = 0; i < n; ++i) { 375 for(int j = 0; j < n; ++j) { 376 if(y[i] > y[j]) { 377 a1 = (xr[i] - xl[j]) / (y[i] - y[j]); 378 a2 = (xl[i] - xr[j]) / (y[i] - y[j]); 379 q.pb({a1, 1}); 380 q.pb({a2, 2}); 381 382 a1 = (xl[i] - xl[j]) / (y[i] - y[j]); 383 a2 = (xr[i] - xr[j]) / (y[i] - y[j]); 384 events.pb({a1, {i, j}}); 385 events.pb({a2, {-i - 1, j}}); 386 } 387 } 388 } 389 390 if(q.empty()) { 391 cout << fixed << setprecision(9) << mx_x - mn_x << endl; 392 return 0; 393 } 394 395 sort(q.rbegin(), q.rend()); 396 int cnt = 0; 397 double last = 0; 398 for(auto i : q) { 399 if(i.y == 2) { 400 --cnt; 401 if(!cnt) { 402 events.pb({i.x, {-1e9, -1e9}}); 403 } 404 } 405 else { 406 if(!cnt) { 407 events.pb({i.x, {-1e9, -1e9}}); 408 } 409 ++cnt; 410 } 411 } 412 sort(events.rbegin(), events.rend()); 413 double ans = 1e18, ang; 414 last = -1e18; 415 for(auto i : events) { 416 if(i.y.x == i.y.y) { 417 unordered_set<int> s; 418 vector<int> to_check; 419 for(auto j : prom_left) { 420 s.insert(j.y.x); 421 if(j.y.x == ind_l) { 422 to_check.pb(j.y.y); 423 } 424 } 425 prom_left.clear(); 426 for(auto j : to_check) { 427 if(!s.count(j)) { 428 ind_l = j; 429 break; 430 } 431 } 432 s.clear(); 433 to_check.clear(); 434 435 for(auto j : prom_right) { 436 s.insert(j.y.y); 437 if(j.y.y == ind_r) { 438 to_check.pb(-j.y.x - 1); 439 } 440 } 441 prom_right.clear(); 442 for(auto j : to_check) { 443 if(!s.count(j)) { 444 ind_r = j; 445 break; 446 } 447 } 448 s.clear(); 449 to_check.clear(); 450 451 double res = point_pr(xr[ind_r], y[ind_r], i.x) - point_pr(xl[ind_l], y[ind_l], i.x); 452 if(ans > res) { 453 ans = res; 454 ang = i.x; 455 } 456 } 457 else if(i.y.x < 0) { 458 if(abs(i.x - last) > eps) { 459 unordered_set<int> s; 460 vector<int> to_check; 461 for(auto j : prom_right) { 462 s.insert(j.y.y); 463 if(j.y.y == ind_r) { 464 to_check.pb(-j.y.x - 1); 465 } 466 } 467 prom_right.clear(); 468 for(auto j : to_check) { 469 if(!s.count(j)) { 470 ind_r = j; 471 break; 472 } 473 } 474 s.clear(); 475 to_check.clear(); 476 } 477 prom_right.pb(i); 478 } 479 else { 480 if(abs(i.x - last) > eps) { 481 unordered_set<int> s; 482 vector<int> to_check; 483 for(auto j : prom_left) { 484 s.insert(j.y.x); 485 if(j.y.x == ind_l) { 486 to_check.pb(j.y.y); 487 } 488 } 489 prom_left.clear(); 490 for(auto j : to_check) { 491 if(!s.count(j)) { 492 ind_l = j; 493 break; 494 } 495 } 496 s.clear(); 497 to_check.clear(); 498 } 499 prom_left.pb(i); 500 } 501 last = i.x; 502 } 503 cout << fixed << setprecision(9) << ans << endl; 504 return 0; 505 } 506 ```