1555.md (8255B)
1 Source: https://codeforces.com/blog/entry/93389 2 3 [1555A - PizzaForces](/contest/1555/problem/A "Educational Codeforces Round 112 (Rated for Div. 2)") 4 5 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 6 7 **Tutorial** 8 9 Tutorial is loading... 10 11 **Solution (Neon)** 12 13 ``` 14 #include <bits/stdc++.h> 15 16 using namespace std; 17 18 int main() { 19 int t; 20 cin >> t; 21 while (t--) { 22 long long n; 23 cin >> n; 24 cout << max(6LL, n + 1) / 2 * 5 << '\n'; 25 } 26 } 27 ``` 28 29 [1555B - Two Tables](/contest/1555/problem/B "Educational Codeforces Round 112 (Rated for Div. 2)") 30 31 Idea: [adedalic](/profile/adedalic "International Master adedalic") 32 33 **Tutorial** 34 35 Tutorial is loading... 36 37 **Solution (adedalic)** 38 39 ``` 40 #include<bits/stdc++.h> 41 42 using namespace std; 43 44 #define fore(i, l, r) for(int i = int(l); i < int(r); i++) 45 #define sz(a) int((a).size()) 46 47 #define x first 48 #define y second 49 50 typedef long long li; 51 typedef pair<int, int> pt; 52 53 const int INF = int(1e9); 54 55 int W, H; 56 int x1, y1, x2, y2; 57 int w, h; 58 59 inline bool read() { 60 if(!(cin >> W >> H)) 61 return false; 62 cin >> x1 >> y1 >> x2 >> y2; 63 cin >> w >> h; 64 return true; 65 } 66 67 inline void solve() { 68 int ans = INF; 69 if (x2 - x1 + w <= W) { 70 ans = min(ans, max(0, w - x1)); 71 ans = min(ans, max(0, x2 - (W - w))); 72 } 73 if (y2 - y1 + h <= H) { 74 ans = min(ans, max(0, h - y1)); 75 ans = min(ans, max(0, y2 - (H - h))); 76 } 77 if (ans == INF) 78 cout << -1 << endl; 79 else 80 cout << double(ans) << endl; 81 } 82 83 int main() { 84 #ifdef _DEBUG 85 freopen("input.txt", "r", stdin); 86 #endif 87 cout << fixed << setprecision(9); 88 int t; cin >> t; 89 while(t--) { 90 (read()); 91 solve(); 92 } 93 return 0; 94 } 95 ``` 96 97 [1555C - Coin Rows](/contest/1555/problem/C "Educational Codeforces Round 112 (Rated for Div. 2)") 98 99 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 100 101 **Tutorial** 102 103 Tutorial is loading... 104 105 **Solution (awoo)** 106 107 ``` 108 #include <bits/stdc++.h> 109 110 #define forn(i, n) for (int i = 0; i < int(n); i++) 111 112 using namespace std; 113 114 const int INF = 2e9 + 10; 115 116 int main() { 117 int t; 118 scanf("%d", &t); 119 forn(_, t){ 120 int n; 121 scanf("%d", &n); 122 vector<vector<int>> a(2, vector<int>(n)); 123 forn(i, 2) forn(j, n) 124 scanf("%d", &a[i][j]); 125 int ans = INF; 126 int sum1 = 0, sum2 = 0; 127 forn(i, n) sum1 += a[0][i]; 128 forn(i, n){ 129 sum1 -= a[0][i]; 130 ans = min(ans, max(sum1, sum2)); 131 sum2 += a[1][i]; 132 } 133 printf("%d\n", ans); 134 } 135 } 136 ``` 137 138 [1555D - Say No to Palindromes](/contest/1555/problem/D "Educational Codeforces Round 112 (Rated for Div. 2)") 139 140 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 141 142 **Tutorial** 143 144 Tutorial is loading... 145 146 **Solution (Neon)** 147 148 ``` 149 #include <bits/stdc++.h> 150 151 using namespace std; 152 153 int main() { 154 ios_base::sync_with_stdio(false); 155 cin.tie(NULL); 156 int n, m; 157 cin >> n >> m; 158 string s; 159 cin >> s; 160 vector<vector<int>> pr(6, vector<int>(n + 1)); 161 string t = "abc"; 162 int cur = 0; 163 do { 164 for (int i = 0; i < n; ++i) 165 pr[cur][i + 1] = pr[cur][i] + (s[i] != t[i % 3]); 166 ++cur; 167 } while (next_permutation(t.begin(), t.end())); 168 while (m--) { 169 int l, r; 170 cin >> l >> r; 171 int ans = n; 172 for (int i = 0; i < 6; ++i) 173 ans = min(ans, pr[i][r] - pr[i][l - 1]); 174 cout << ans << "\n"; 175 } 176 } 177 ``` 178 179 [1555E - Boring Segments](/contest/1555/problem/E "Educational Codeforces Round 112 (Rated for Div. 2)") 180 181 Idea: [vovuh](/profile/vovuh "Master vovuh"), [adedalic](/profile/adedalic "International Master adedalic") 182 183 **Tutorial** 184 185 Tutorial is loading... 186 187 **Solution (awoo)** 188 189 ``` 190 #include <bits/stdc++.h> 191 192 #define forn(i, n) for (int i = 0; i < int(n); i++) 193 194 using namespace std; 195 196 const int INF = 1e9; 197 198 vector<int> t, ps; 199 200 void push(int v){ 201 if (v * 2 + 1 < int(ps.size())){ 202 ps[v * 2] += ps[v]; 203 ps[v * 2 + 1] += ps[v]; 204 } 205 t[v] += ps[v]; 206 ps[v] = 0; 207 } 208 209 void upd(int v, int l, int r, int L, int R, int val){ 210 push(v); 211 if (L >= R) 212 return; 213 if (l == L && r == R){ 214 ps[v] += val; 215 push(v); 216 return; 217 } 218 int m = (l + r) / 2; 219 upd(v * 2, l, m, L, min(m, R), val); 220 upd(v * 2 + 1, m, r, max(m, L), R, val); 221 t[v] = min(t[v * 2], t[v * 2 + 1]); 222 } 223 224 int get(){ 225 return t[1] + ps[1]; 226 } 227 228 struct seg{ 229 int l, r, w; 230 }; 231 232 int main() { 233 int n, m; 234 scanf("%d%d", &n, &m); 235 vector<seg> a(n); 236 forn(i, n){ 237 scanf("%d%d%d", &a[i].l, &a[i].r, &a[i].w); 238 --a[i].l, --a[i].r; 239 } 240 --m; 241 sort(a.begin(), a.end(), [](const seg &a, const seg &b){ 242 return a.w < b.w; 243 }); 244 t.resize(4 * m); 245 ps.resize(4 * m); 246 int ans = INF; 247 int j = 0; 248 forn(i, n){ 249 while (j < n && get() == 0){ 250 upd(1, 0, m, a[j].l, a[j].r, 1); 251 ++j; 252 } 253 if (get() == 0){ 254 break; 255 } 256 ans = min(ans, a[j - 1].w - a[i].w); 257 upd(1, 0, m, a[i].l, a[i].r, -1); 258 } 259 printf("%d\n", ans); 260 return 0; 261 } 262 ``` 263 264 [1555F - Good Graph](/contest/1555/problem/F "Educational Codeforces Round 112 (Rated for Div. 2)") 265 266 Idea: [adedalic](/profile/adedalic "International Master adedalic") 267 268 **Tutorial** 269 270 Tutorial is loading... 271 272 **Solution (adedalic)** 273 274 ``` 275 #include<bits/stdc++.h> 276 277 using namespace std; 278 279 #define fore(i, l, r) for(int i = int(l); i < int(r); i++) 280 #define sz(a) int((a).size()) 281 282 #define x first 283 #define y second 284 285 typedef long long li; 286 typedef pair<int, int> pt; 287 288 template<class A, class B> ostream& operator <<(ostream& out, const pair<A, B> &p) { 289 return out << "(" << p.x << ", " << p.y << ")"; 290 } 291 template<class A> ostream& operator <<(ostream& out, const vector<A> &v) { 292 fore(i, 0, sz(v)) { 293 if(i) out << " "; 294 out << v[i]; 295 } 296 return out; 297 } 298 299 const int INF = int(1e9); 300 const li INF64 = li(1e18); 301 302 int n, q; 303 vector< array<int, 3> > es; 304 305 inline bool read() { 306 if(!(cin >> n >> q)) 307 return false; 308 es.resize(q); 309 fore (i, 0, q) { 310 cin >> es[i][0] >> es[i][1] >> es[i][2]; 311 es[i][0]--; 312 es[i][1]--; 313 } 314 return true; 315 } 316 317 vector< vector<pt> > g; 318 319 const int LOG = 19; 320 vector<int> up[LOG]; 321 vector<int> tin, tout; 322 vector<int> xr; 323 int T = 0; 324 325 void dfs(int v, int p, int curXor) { 326 tin[v] = T++; 327 xr[v] = curXor; 328 up[0][v] = p; 329 fore (pw, 1, LOG) 330 up[pw][v] = up[pw - 1][up[pw - 1][v]]; 331 332 for (auto [to, w] : g[v]) { 333 if (to == p) 334 continue; 335 dfs(to, v, curXor ^ w); 336 } 337 tout[v] = T; 338 } 339 340 void buildLCA() { 341 fore (pw, 0, LOG) 342 up[pw].resize(n); 343 tin.assign(n, -1); 344 tout.assign(n, -1); 345 xr.assign(n, 0); 346 347 T = 0; 348 fore (v, 0, n) { 349 if (tin[v] != -1) 350 continue; 351 dfs(v, v, 0); 352 } 353 } 354 355 int isPar(int p, int v) { 356 return tin[p] <= tin[v] && tout[v] <= tout[p]; 357 } 358 359 int lca(int u, int v) { 360 if (isPar(u, v)) return u; 361 if (isPar(v, u)) return v; 362 363 for (int pw = LOG - 1; pw >= 0; pw--) { 364 if (!isPar(up[pw][v], u)) 365 v = up[pw][v]; 366 } 367 return up[0][v]; 368 } 369 370 vector<int> par, rk; 371 372 void init(int n) { 373 par.assign(n, 0); 374 iota(par.begin(), par.end(), 0); 375 rk.assign(n, 1); 376 } 377 378 int top(int v) { 379 if (par[v] != v) 380 return par[v] = top(par[v]); 381 return v; 382 } 383 384 bool unite(int u, int v) { 385 u = top(u); 386 v = top(v); 387 if (u == v) 388 return false; 389 if (rk[u] < rk[v]) 390 swap(u, v); 391 par[v] = u; 392 rk[u] += rk[v]; 393 return true; 394 } 395 396 vector<int> F; 397 void inc(int pos, int val) { 398 for(; pos < sz(F); pos |= pos + 1) 399 F[pos] += val; 400 } 401 int sum(int pos) { 402 int ans = 0; 403 for(; pos >= 0; pos = (pos & (pos + 1)) - 1) 404 ans += F[pos]; 405 return ans; 406 } 407 408 void addOnPath(int v, int l) { 409 while (v != l) { 410 inc(tin[v], 1); 411 inc(tout[v], -1); 412 v = up[0][v]; 413 } 414 } 415 416 inline void solve() { 417 init(n); 418 g.resize(n); 419 420 vector<int> ans(q, -1); 421 fore (i, 0, q) { 422 int u = es[i][0]; 423 int v = es[i][1]; 424 int x = es[i][2]; 425 426 if (unite(u, v)) { 427 ans[i] = 1; 428 g[u].emplace_back(v, x); 429 g[v].emplace_back(u, x); 430 } 431 } 432 433 buildLCA(); 434 F.assign(2 * n + 5, 0); 435 436 fore (i, 0, q) { 437 if (ans[i] != -1) 438 continue; 439 440 ans[i] = 0; 441 int u = es[i][0]; 442 int v = es[i][1]; 443 int x = es[i][2]; 444 445 int xorPath = xr[u] ^ xr[v]; 446 if ((xorPath ^ x) != 1) 447 continue; 448 449 int l = lca(u, v); 450 int usedOnPath = sum(tin[u]) + sum(tin[v]) - 2 * sum(tin[l]); 451 if (usedOnPath > 0) 452 continue; 453 454 ans[i] = 1; 455 addOnPath(u, l); 456 addOnPath(v, l); 457 } 458 459 for (int res : ans) 460 cout << (res ? "YES" : "NO") << '\n'; 461 } 462 463 int main() { 464 #ifdef _DEBUG 465 freopen("input.txt", "r", stdin); 466 int tt = clock(); 467 #endif 468 ios_base::sync_with_stdio(false); 469 cin.tie(0), cout.tie(0); 470 cout << fixed << setprecision(15); 471 472 if(read()) { 473 solve(); 474 475 #ifdef _DEBUG 476 cerr << "TIME = " << clock() - tt << endl; 477 tt = clock(); 478 #endif 479 } 480 return 0; 481 } 482 ```