1163.md (12098B)
1 Source: https://codeforces.com/blog/entry/66943 2 3 Hello everyone, this is the editorial for [Codeforces Round 558 (Div. 2)](/contest/1163 "Codeforces Round 558 (Div. 2)"). I hope you enjoy the problem as well as I did! 4 5 [1163A - Eating Soup](/contest/1163/problem/A "Codeforces Round 558 (Div. 2)") 6 7 Author: [xuandadenbenem](/profile/xuandadenbenem "Expert xuandadenbenem") 8 9 **Tutorial** 10 11 Tutorial is loading... 12 13 **Implementation** 14 15 ``` 16 #include <iostream> 17 18 using namespace std; 19 20 int main () 21 { 22 int n, m; 23 cin >> n >> m; 24 cout << (m ? min(m, n - m) : 1) << endl; 25 return 0; 26 } 27 ``` 28 29 [1163B2 - Cat Party (Hard Edition)](/contest/1163/problem/B2 "Codeforces Round 558 (Div. 2)") 30 31 Author: [Shirone](/profile/Shirone "Specialist Shirone") 32 33 **Tutorial** 34 35 Tutorial is loading... 36 37 **Implementation** 38 39 ``` 40 #include <iostream> 41 #include <stdio.h> 42 using namespace std; 43 44 const int N = 1e5 + 10; 45 46 int n, color, ans, mx, f[N], cnt[N]; 47 48 int main() 49 { 50 scanf("%d", &n); 51 for (int i = 1; i <= n; i++) 52 { 53 scanf("%d", &color); 54 cnt[f[color]]--; 55 f[color]++; 56 cnt[f[color]]++; 57 mx = max(mx, f[color]); 58 bool ok = false; 59 if (cnt[1] == i) // every color has occurence of 1 60 ok = true; 61 else if (cnt[i] == 1) // only one color has the maximum occurence and the occurence is i 62 ok = true; 63 else if (cnt[1] == 1 && cnt[mx] * mx == i - 1) // one color has occurence of 1 and other colors have the same occurence 64 ok = true; 65 else if (cnt[mx - 1] * (mx - 1) == i - mx && cnt[mx] == 1) // one color has the occurence 1 more than any other color 66 ok = true; 67 if (ok) 68 ans = i; 69 } 70 printf("%d", ans); 71 return 0; 72 } 73 ``` 74 75 [1163C2 - Power Transmission (Hard Edition)](/contest/1163/problem/C2 "Codeforces Round 558 (Div. 2)") 76 77 Author: [GreymaneSilverfang](/profile/GreymaneSilverfang "Candidate Master GreymaneSilverfang") 78 79 **Tutorial** 80 81 Tutorial is loading... 82 83 **Implementation** 84 85 ``` 86 #include <cstdio> 87 #include <map> 88 #include <set> 89 #include <utility> 90 const int N = 1001; 91 int x[N], y[N]; 92 std::map<std::pair<int,int>,std::set<long long>> slope_map; 93 94 int gcd(int a, int b) 95 { 96 if (a == 0) 97 return b; 98 return gcd(b % a, a); 99 } 100 101 int main() 102 { 103 int n; scanf("%d", &n); 104 for (int i = 1; i <= n; ++i) 105 scanf("%d%d", &x[i], &y[i]); 106 long long total = 0, res = 0; 107 for (int i = 1; i <= n - 1; ++i) 108 for (int j = i + 1; j <= n; ++j) 109 { 110 int x1 = x[i], y1 = y[i], x2 = x[j], y2 = y[j]; 111 // construct a line passing through (x1, y1) and (x2, y2) 112 // line is expressed as equation ax - by = c with constant a, b, c 113 int a = y1 - y2, b = x1 - x2; 114 // simplify equation 115 int d = gcd(a, b); a /= d, b /= d; 116 if (a < 0 || (a == 0 && b < 0)) 117 { 118 a = -a; 119 b = -b; 120 } 121 // lines with the same slope (same a, b) are stored in a map 122 std::pair<int,int> slope(a, b); 123 long long c = 1LL * a * x1 - 1LL * b * y1; 124 if (!slope_map[slope].count(c)) 125 { 126 ++total; 127 slope_map[slope].insert(c); 128 // if this line is new, it intersects every line with different slope 129 res += total - slope_map[slope].size(); 130 } 131 } 132 printf("%lld\n", res); 133 } 134 ``` 135 136 [1163D - Mysterious Code](/contest/1163/problem/D "Codeforces Round 558 (Div. 2)") 137 138 Author: [Kuroni](/profile/Kuroni "International Master Kuroni") 139 140 **Tutorial** 141 142 Tutorial is loading... 143 144 **Implementation** 145 146 ``` 147 #include <iostream> 148 #include <cstdio> 149 #include <cstring> 150 using namespace std; 151 152 const int K = 1005, N = 55, M = 55, INF = 1E9 + 7; 153 154 int k, n, m; 155 int kmp_s[N], nxt_s[N][26], kmp_t[M], nxt_t[M][26]; 156 int dp[K][N][M]; 157 char code[K], s[N], t[M]; 158 159 void init(char s[], int n, int kmp[], int nxt[][26]) 160 { 161 kmp[1] = 0; 162 for (int i = 2; i <= n; i++) 163 { 164 int cur = kmp[i - 1]; 165 while (cur > 0 && s[cur + 1] != s[i]) 166 cur = kmp[cur]; 167 if (s[cur + 1] == s[i]) 168 ++cur; 169 kmp[i] = cur; 170 } 171 172 for (int i = 0; i <= n; i++) 173 for (char c = 'a'; c <= 'z'; c++) 174 { 175 int cur = i; 176 while (cur > 0 && s[cur + 1] != c) 177 cur = kmp[cur]; 178 if (s[cur + 1] == c) 179 ++cur; 180 nxt[i][c - 'a'] = cur; 181 } 182 } 183 184 int main() 185 { 186 scanf("%s%s%s", code + 1, s + 1, t + 1); 187 k = strlen(code + 1); n = strlen(s + 1); m = strlen(t + 1); 188 init(s, n, kmp_s, nxt_s); init(t, m, kmp_t, nxt_t); 189 for (int i = 0; i <= k; i++) 190 for (int ks = 0; ks <= n; ks++) 191 for (int kt = 0; kt <= m; kt++) 192 dp[i][ks][kt] = -INF; 193 dp[0][0][0] = 0; 194 for (int i = 0; i < k; i++) 195 for (int ks = 0; ks <= n; ks++) 196 for (int kt = 0; kt <= m; kt++) 197 for (char c = 'a'; c <= 'z'; c++) 198 if (code[i + 1] == '*' || code[i + 1] == c) // we now add/replace the (i + 1)-th character 199 { 200 int ns = nxt_s[ks][c - 'a'], nt = nxt_t[kt][c - 'a']; 201 int tmp = dp[i][ks][kt] + (ns == n) - (nt == m); // add the new occurrences if any 202 dp[i + 1][ns][nt] = max(dp[i + 1][ns][nt], tmp); 203 } 204 int ma = -INF; 205 for (int ks = 0; ks <= n; ks++) 206 for (int kt = 0; kt <= m; kt++) 207 ma = max(ma, dp[k][ks][kt]); 208 printf("%d\n", ma); 209 } 210 ``` 211 212 [1163E - Magical Permutation](/contest/1163/problem/E "Codeforces Round 558 (Div. 2)") 213 214 Author: [Kuroni](/profile/Kuroni "International Master Kuroni") 215 216 **Tutorial** 217 218 Tutorial is loading... 219 220 **Implementation** 221 222 ``` 223 #include <iostream> 224 #include <cstdio> 225 #include <vector> 226 #include <algorithm> 227 using namespace std; 228 229 const int N = 200005; 230 231 int n, a[N]; 232 vector<int> basis, vec; 233 234 void add(int u) 235 { 236 int tmp = u; 237 // we keep the basis sorted in decreasing order 238 for (int &v : basis) 239 u = min(u, u ^ v); 240 if (u > 0) // u is a new element in the basis 241 { 242 basis.push_back(u); 243 vec.push_back(tmp); 244 // now we move u up until the basis is decreasingly sorted again 245 for (int i = basis.size() - 1; i > 0; i--) 246 if (basis[i] > basis[i - 1]) 247 swap(basis[i], basis[i - 1]); 248 else 249 break; 250 } 251 } 252 253 void gray_code(int size) 254 { 255 vector<int> ans = {0}; 256 for (int i = 0; i < size; i++) 257 for (int j = (1 << i) - 1; j >= 0; j--) 258 ans.push_back(ans[j] ^ vec[i]); 259 for (int &v : ans) 260 printf("%d ", v); 261 } 262 263 int main() 264 { 265 scanf("%d", &n); 266 for (int i = 0; i < n; i++) 267 scanf("%d", a + i); 268 sort(a, a + n); 269 int pt = 0, x = 0; 270 for (int i = 1; i < 20; i++) 271 { 272 for (; pt < n && a[pt] < (1 << i); pt++) 273 add(a[pt]); 274 if (basis.size() == i) 275 x = i; 276 } 277 basis.clear(); 278 vec.clear(); 279 for (int i = 0; i < n && a[i] < (1 << x); i++) 280 add(a[i]); 281 printf("%d\n", x); 282 gray_code(x); 283 } 284 ``` 285 286 **Implementation with DFS** 287 288 ``` 289 #include <iostream> 290 #include <cstdio> 291 #include <vector> 292 #include <algorithm> 293 using namespace std; 294 295 const int N = 200005, MX = 1E6 + 5; 296 297 int n, x = 0, a[N]; 298 bool vis[MX]; 299 vector<int> basis, vec, ans; 300 301 void add(int u) 302 { 303 int tmp = u; 304 for (int &v : basis) 305 u = min(u, u ^ v); 306 if (u > 0) 307 { 308 basis.push_back(u); 309 vec.push_back(tmp); 310 for (int i = basis.size() - 1; i > 0; i--) 311 if (basis[i] > basis[i - 1]) 312 swap(basis[i], basis[i - 1]); 313 else 314 break; 315 } 316 } 317 318 void DFS(int u, int it = 0) 319 { 320 ans.push_back(u); 321 vis[u] = true; 322 if (it == (1 << x) - 1) 323 return; 324 for (int &v : vec) 325 if (!vis[u ^ v]) 326 { 327 DFS(u ^ v, it + 1); 328 return; 329 } 330 } 331 332 int main() 333 { 334 scanf("%d", &n); 335 for (int i = 0; i < n; i++) 336 scanf("%d", a + i); 337 sort(a, a + n); 338 int pt = 0; 339 for (int i = 1; i < 20; i++) 340 { 341 for (; pt < n && a[pt] < (1 << i); pt++) 342 add(a[pt]); 343 if (basis.size() == i) 344 x = i; 345 } 346 basis.clear(); 347 vec.clear(); 348 for (int i = 0; i < n && a[i] < (1 << x); i++) 349 add(a[i]); 350 printf("%d\n", x); 351 DFS(0); 352 for (int &v : ans) 353 printf("%d ", v); 354 } 355 ``` 356 357 [1163F - Indecisive Taxi Fee](/contest/1163/problem/F "Codeforces Round 558 (Div. 2)") 358 359 Author: [Kuroni](/profile/Kuroni "International Master Kuroni") 360 361 **Tutorial** 362 363 Tutorial is loading... 364 365 **Implementation** 366 367 ``` 368 #include <iostream> 369 #include <cstdio> 370 #include <vector> 371 #include <queue> 372 using namespace std; 373 374 const int N = 2E5 + 5, M = 2E5 + 5; 375 const long long INF = 1E18 + 7; 376 377 int n, m, q, ed, nw, mx, u[M], v[M], w[M], ind[M]; 378 int tr[N], le[N], ri[N]; 379 bool on_path[N]; 380 long long dis[2][N]; 381 382 struct TNode 383 { 384 int u; 385 long long val; 386 387 TNode(int _u, long long _val) 388 { 389 u = _u; 390 val = _val; 391 } 392 393 inline bool operator>(const TNode &oth) const 394 { 395 return val > oth.val; 396 } 397 }; 398 priority_queue<TNode, vector<TNode>, greater<TNode>> pq; 399 400 struct TEdge 401 { 402 int v, w, ind; 403 404 TEdge(int _v, int _w, int _ind) 405 { 406 v = _v; 407 w = _w; 408 ind = _ind; 409 } 410 }; 411 vector<TEdge> adj[N]; 412 413 struct TTree 414 { 415 #define m (l + r) / 2 416 #define lc i * 2 417 #define rc i * 2 + 1 418 419 long long tr[4 * M]; 420 421 void build(int l, int r, int i) 422 { 423 tr[i] = INF; 424 if (l == r) 425 return; 426 build(l, m, lc); 427 build(m + 1, r, rc); 428 } 429 430 void upd(int l, int r, int i, int L, int R, long long v) 431 { 432 if (l > R || r < L || L > R) 433 return; 434 if (L <= l && r <= R) 435 { 436 tr[i] = min(tr[i], v); 437 return; 438 } 439 upd(l, m, lc, L, R, v); 440 upd(m + 1, r, rc, L, R, v); 441 } 442 443 long long que(int l, int r, int i, int u) 444 { 445 if (l == r) 446 return tr[i]; 447 return min(tr[i], u <= m ? que(l, m, lc, u) : que(m + 1, r, rc, u)); 448 } 449 450 #undef m 451 #undef lc 452 #undef rc 453 } seg; 454 455 void dijkstra(int st, long long dis[], int get = 0) 456 { 457 fill(dis + 1, dis + n + 1, INF); 458 pq.push(TNode(st, dis[st] = 0)); 459 while (!pq.empty()) 460 { 461 TNode u = pq.top(); pq.pop(); 462 if (u.val > dis[u.u]) 463 continue; 464 for (TEdge &v : adj[u.u]) 465 if (dis[v.v] > u.val + v.w) 466 { 467 tr[v.v] = v.ind; 468 if (get == 1 && !on_path[v.v]) 469 le[v.v] = le[u.u]; 470 else if (get == 2 && !on_path[v.v]) 471 ri[v.v] = ri[u.u]; 472 pq.push(TNode(v.v, dis[v.v] = u.val + v.w)); 473 } 474 } 475 } 476 477 void trace() 478 { 479 on_path[1] = true; le[1] = ri[1] = 0; 480 for (int i = 1, cur = 1; cur != n; i++) 481 { 482 int edge = tr[cur]; 483 ind[edge] = mx = i; 484 cur = u[edge] ^ v[edge] ^ cur; 485 on_path[cur] = true; 486 le[cur] = ri[cur] = i; 487 } 488 } 489 490 int main() 491 { 492 scanf("%d%d%d", &n, &m, &q); 493 for (int i = 1; i <= m; i++) 494 { 495 scanf("%d%d%d", u + i, v + i, w + i); 496 ind[i] = -1; 497 adj[u[i]].push_back(TEdge(v[i], w[i], i)); 498 adj[v[i]].push_back(TEdge(u[i], w[i], i)); 499 } 500 dijkstra(n, dis[1]); // reverse the initial dijkstra for the trace to increase from 1 -> n 501 trace(); 502 dijkstra(1, dis[0], 1); 503 dijkstra(n, dis[1], 2); 504 seg.build(1, mx, 1); 505 for (int i = 1; i <= m; i++) 506 if (ind[i] == -1) 507 { 508 seg.upd(1, mx, 1, le[u[i]] + 1, ri[v[i]], dis[0][u[i]] + w[i] + dis[1][v[i]]); 509 seg.upd(1, mx, 1, le[v[i]] + 1, ri[u[i]], dis[0][v[i]] + w[i] + dis[1][u[i]]); 510 } 511 while (q--) 512 { 513 scanf("%d%d", &ed, &nw); 514 long long ans; 515 if (ind[ed] > 0) 516 { 517 ans = dis[0][n] - w[ed] + nw; 518 if (nw > w[ed]) 519 ans = min(ans, seg.que(1, mx, 1, ind[ed])); 520 } 521 else 522 { 523 ans = dis[0][n]; 524 if (nw < w[ed]) 525 { 526 ans = min(ans, dis[0][u[ed]] + nw + dis[1][v[ed]]); 527 ans = min(ans, dis[0][v[ed]] + nw + dis[1][u[ed]]); 528 } 529 } 530 printf("%lld\n", ans); 531 } 532 } 533 ```