1633.md (10356B)
1 Source: https://codeforces.com/blog/entry/99539 2 3 [1633A - Div. 7](/contest/1633/problem/A "Educational Codeforces Round 122 (Rated for Div. 2)") 4 5 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest"), preparation: [BledDest](/profile/BledDest "International Grandmaster BledDest") 6 7 **Tutorial** 8 9 Tutorial is loading... 10 11 **Solution (BledDest)** 12 13 ``` 14 t = int(input()) 15 for i in range(t): 16 n = int(input()) 17 if n % 7 == 0: 18 print(n) 19 else: 20 ans = -1 21 for j in range(10): 22 if (n - n % 10 + j) % 7 == 0: 23 ans = n - n % 10 + j 24 print(ans) 25 ``` 26 27 [1633B - Minority](/contest/1633/problem/B "Educational Codeforces Round 122 (Rated for Div. 2)") 28 29 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest"), preparation: [awoo](/profile/awoo "Grandmaster awoo") and [Neon](/profile/Neon "Candidate Master Neon") 30 31 **Tutorial** 32 33 Tutorial is loading... 34 35 **Solution (awoo)** 36 37 ``` 38 for _ in range(int(input())): 39 s = input() 40 print(min((len(s) - 1) // 2, s.count('0'), s.count('1'))) 41 ``` 42 43 [1633C - Kill the Monster](/contest/1633/problem/C "Educational Codeforces Round 122 (Rated for Div. 2)") 44 45 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest"), preparation: [Neon](/profile/Neon "Candidate Master Neon") 46 47 **Tutorial** 48 49 Tutorial is loading... 50 51 **Solution (awoo)** 52 53 ``` 54 for _ in range(int(input())): 55 hc, dc = map(int, input().split()) 56 hm, dm = map(int, input().split()) 57 k, w, a = map(int, input().split()) 58 for i in range(k + 1): 59 nhc = hc + i * a 60 ndc = dc + (k - i) * w 61 if (hm + ndc - 1) // ndc <= (nhc + dm - 1) // dm: 62 print("YES") 63 break 64 else: 65 print("NO") 66 ``` 67 68 [1633D - Make Them Equal](/contest/1633/problem/D "Educational Codeforces Round 122 (Rated for Div. 2)") 69 70 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest"), preparation: [Neon](/profile/Neon "Candidate Master Neon") 71 72 **Tutorial** 73 74 Tutorial is loading... 75 76 **Solution (Neon)** 77 78 ``` 79 #include <bits/stdc++.h> 80 81 using namespace std; 82 83 const int N = 1001; 84 85 int main() { 86 vector<int> d(N, N); 87 d[1] = 0; 88 for (int i = 1; i < N; ++i) { 89 for (int x = 1; x <= i; ++x) { 90 int j = i + i / x; 91 if (j < N) d[j] = min(d[j], d[i] + 1); 92 } 93 } 94 95 int t; 96 cin >> t; 97 while (t--) { 98 int n, k; 99 cin >> n >> k; 100 vector<int> b(n), c(n); 101 for (int &x : b) cin >> x; 102 for (int &x : c) cin >> x; 103 int sum = 0; 104 for (int x : b) sum += d[x]; 105 k = min(k, sum); 106 vector<int> dp(k + 1, 0); 107 for (int i = 0; i < n; ++i) { 108 for (int j = k - d[b[i]]; j >= 0; j--) { 109 dp[j + d[b[i]]] = max(dp[j + d[b[i]]], dp[j] + c[i]); 110 } 111 } 112 cout << *max_element(dp.begin(), dp.end()) << '\n'; 113 } 114 } 115 ``` 116 117 [1633E - Spanning Tree Queries](/contest/1633/problem/E "Educational Codeforces Round 122 (Rated for Div. 2)") 118 119 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest"), preparation: [awoo](/profile/awoo "Grandmaster awoo") 120 121 **Tutorial** 122 123 Tutorial is loading... 124 125 **Solution (awoo)** 126 127 ``` 128 #include <bits/stdc++.h> 129 130 #define forn(i, n) for (int i = 0; i < int(n); i++) 131 132 using namespace std; 133 134 struct edge{ 135 int v, u, w; 136 }; 137 138 vector<int> pr, rk; 139 140 int getp(int a){ 141 return a == pr[a] ? a : pr[a] = getp(pr[a]); 142 } 143 144 bool unite(int a, int b){ 145 a = getp(a), b = getp(b); 146 if (a == b) return false; 147 if (rk[a] < rk[b]) swap(a, b); 148 rk[a] += rk[b]; 149 pr[b] = a; 150 return true; 151 } 152 153 int main() { 154 int n, m; 155 scanf("%d%d", &n, &m); 156 pr.resize(n); 157 rk.resize(n); 158 vector<edge> es(m); 159 forn(i, m){ 160 scanf("%d%d%d", &es[i].v, &es[i].u, &es[i].w); 161 --es[i].v, --es[i].u; 162 es[i].w *= 2; 163 } 164 vector<int> ev(1, 0); 165 forn(i, m) forn(j, i + 1) ev.push_back((es[i].w + es[j].w) / 2); 166 sort(ev.begin(), ev.end()); 167 ev.resize(unique(ev.begin(), ev.end()) - ev.begin()); 168 vector<long long> base; 169 vector<int> cnt; 170 for (int x : ev){ 171 sort(es.begin(), es.end(), [&x](const edge &a, const edge &b){ 172 int wa = abs(a.w - x); 173 int wb = abs(b.w - x); 174 if (wa != wb) return wa < wb; 175 return a.w > b.w; 176 }); 177 forn(i, n) pr[i] = i, rk[i] = 1; 178 long long cur_base = 0; 179 int cur_cnt = 0; 180 for (const auto &e : es) if (unite(e.v, e.u)){ 181 cur_base += abs(e.w - x); 182 cur_cnt += x < e.w; 183 } 184 base.push_back(cur_base); 185 cnt.push_back(cur_cnt); 186 } 187 int p, k, a, b, c; 188 scanf("%d%d%d%d%d", &p, &k, &a, &b, &c); 189 int x = 0; 190 long long ans = 0; 191 forn(q, k){ 192 if (q < p) scanf("%d", &x); 193 else x = (x * 1ll * a + b) % c; 194 int y = upper_bound(ev.begin(), ev.end(), 2 * x) - ev.begin() - 1; 195 ans ^= (base[y] + (n - 1 - 2 * cnt[y]) * 1ll * (2 * x - ev[y])) / 2; 196 } 197 printf("%lld\n", ans); 198 return 0; 199 } 200 ``` 201 202 [1633F - Perfect Matching](/contest/1633/problem/F "Educational Codeforces Round 122 (Rated for Div. 2)") 203 204 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest"), preparation: [BledDest](/profile/BledDest "International Grandmaster BledDest") 205 206 **Tutorial** 207 208 Tutorial is loading... 209 210 **Solution (BledDest)** 211 212 ``` 213 #include <bits/stdc++.h> 214 215 using namespace std; 216 217 typedef pair<long long, int> val; 218 219 #define x first 220 #define y second 221 222 const int N = 200043; 223 224 val operator +(const val& a, const val& b) 225 { 226 return make_pair(a.x + b.x, a.y + b.y); 227 } 228 229 val operator -(const val& a, const val& b) 230 { 231 return make_pair(a.x - b.x, a.y - b.y); 232 } 233 234 val T[4 * N]; 235 val Tfull[4 * N]; 236 int f[4 * N]; 237 238 val getVal(int v) 239 { 240 if(f[v] == 1) 241 return Tfull[v] - T[v]; 242 return T[v]; 243 } 244 245 void push(int v) 246 { 247 if(f[v] == 1) 248 { 249 f[v] = 0; 250 T[v] = Tfull[v] - T[v]; 251 f[v * 2 + 1] ^= 1; 252 f[v * 2 + 2] ^= 1; 253 } 254 } 255 256 void upd(int v) 257 { 258 Tfull[v] = Tfull[v * 2 + 1] + Tfull[v * 2 + 2]; 259 T[v] = getVal(v * 2 + 1) + getVal(v * 2 + 2); 260 } 261 262 void setVal(int v, int l, int r, int pos, val cur) 263 { 264 if(l == r - 1) 265 { 266 f[v] = 0; 267 Tfull[v] = cur; 268 T[v] = cur; 269 } 270 else 271 { 272 push(v); 273 int m = (l + r) / 2; 274 if(pos < m) 275 setVal(v * 2 + 1, l, m, pos, cur); 276 else 277 setVal(v * 2 + 2, m, r, pos, cur); 278 upd(v); 279 } 280 } 281 282 void flipColor(int v, int l, int r, int L, int R) 283 { 284 if(L >= R) return; 285 if(l == L && r == R) 286 f[v] ^= 1; 287 else 288 { 289 push(v); 290 int m = (l + r) / 2; 291 flipColor(v * 2 + 1, l, m, L, min(m, R)); 292 flipColor(v * 2 + 2, m, r, max(L, m), R); 293 upd(v); 294 } 295 } 296 297 val getVal(int v, int l, int r, int L, int R) 298 { 299 if(L >= R) return make_pair(0ll, 0); 300 if(l == L && r == R) return getVal(v); 301 int m = (l + r) / 2; 302 val ans = make_pair(0ll, 0); 303 push(v); 304 ans = ans + getVal(v * 2 + 1, l, m, L, min(R, m)); 305 ans = ans + getVal(v * 2 + 2, m, r, max(L, m), R); 306 upd(v); 307 return ans; 308 } 309 310 int n; 311 vector<int> g[N]; 312 313 int p[N], siz[N], d[N], nxt[N]; 314 int tin[N], timer; 315 map<pair<int, int>, int> idx; 316 long long sum; 317 int cnt; 318 int active[N]; 319 int active_cnt; 320 321 void dfs_sz(int v) 322 { 323 if (p[v] != -1) 324 { 325 auto it = find(g[v].begin(), g[v].end(), p[v]); 326 if (it != g[v].end()) 327 g[v].erase(it); 328 } 329 siz[v] = 1; 330 for (int &u : g[v]) 331 { 332 p[u] = v; 333 d[u] = d[v] + 1; 334 dfs_sz(u); 335 siz[v] += siz[u]; 336 if (siz[u] > siz[g[v][0]]) 337 swap(u, g[v][0]); 338 } 339 } 340 341 void dfs_hld(int v) 342 { 343 tin[v] = timer++; 344 for (int u : g[v]) 345 { 346 nxt[u] = (u == g[v][0] ? nxt[v] : u); 347 dfs_hld(u); 348 } 349 } 350 351 // [l; r] inclusive 352 void flipSegment(int l, int r) 353 { 354 flipColor(0, 0, n, l, r + 1); 355 } 356 357 // [l; r] inclusive 358 val get(int l, int r) 359 { 360 return getVal(0, 0, n, l, r + 1); 361 } 362 363 void flipPath(int v, int u) 364 { 365 for (; nxt[v] != nxt[u]; u = p[nxt[u]]) 366 { 367 if (d[nxt[v]] > d[nxt[u]]) swap(v, u); 368 flipSegment(tin[nxt[u]], tin[u]); 369 } 370 if (d[v] > d[u]) swap(v, u); 371 flipSegment(tin[v], tin[u]); 372 } 373 374 val getPath(int v, int u) 375 { 376 val res = make_pair(0ll, 0); 377 for (; nxt[v] != nxt[u]; u = p[nxt[u]]) 378 { 379 if (d[nxt[v]] > d[nxt[u]]) swap(v, u); 380 // update res with the result of get() 381 res = res + get(tin[nxt[u]], tin[u]); 382 } 383 if (d[v] > d[u]) swap(v, u); 384 res = res + get(tin[v], tin[u]); 385 return res; 386 } 387 388 void activate_vertex(int x) 389 { 390 int id = 0; 391 if(p[x] != -1) 392 { 393 id = idx[make_pair(x, p[x])]; 394 val v = getPath(0, p[x]); 395 flipPath(0, p[x]); 396 sum -= v.x; 397 cnt -= v.y; 398 v = getPath(0, p[x]); 399 sum += v.x; 400 cnt += v.y; 401 } 402 cnt++; 403 sum += id; 404 setVal(0, 0, n, tin[x], make_pair((long long)(id), 1)); 405 active[x] = 1; 406 active_cnt++; 407 } 408 409 void init_hld(int root = 0) 410 { 411 d[root] = 0; 412 nxt[root] = root; 413 p[root] = -1; 414 timer = 0; 415 dfs_sz(root); 416 dfs_hld(root); 417 } 418 419 int currentSize[N]; 420 421 int dfsSolution(int x, vector<int>& edges) 422 { 423 if(!active[x]) return 0; 424 currentSize[x] = 1; 425 for(auto y : g[x]) 426 if(y != p[x]) 427 currentSize[x] += dfsSolution(y, edges); 428 if(currentSize[x] % 2 == 1) 429 edges.push_back(idx[make_pair(x, p[x])]); 430 return currentSize[x]; 431 } 432 433 void outputSolution() 434 { 435 vector<int> edges; 436 if(cnt * 2 == active_cnt) 437 { 438 dfsSolution(0, edges); 439 sort(edges.begin(), edges.end()); 440 } 441 printf("%d", int(edges.size())); 442 for(auto x : edges) printf(" %d", x); 443 puts(""); 444 fflush(stdout); 445 } 446 447 void processQuery(int v) 448 { 449 activate_vertex(v); 450 if(cnt * 2 == active_cnt) 451 printf("%lld\n", sum); 452 else 453 puts("0"); 454 fflush(stdout); 455 } 456 457 int main() 458 { 459 scanf("%d", &n); 460 for(int i = 1; i < n; i++) 461 { 462 int x, y; 463 scanf("%d %d", &x, &y); 464 --x; 465 --y; 466 g[x].push_back(y); 467 g[y].push_back(x); 468 idx[make_pair(x, y)] = i; 469 idx[make_pair(y, x)] = i; 470 } 471 472 init_hld(); 473 activate_vertex(0); 474 while(true) 475 { 476 int t; 477 scanf("%d", &t); 478 if(t == 3) 479 break; 480 if(t == 2) 481 outputSolution(); 482 if(t == 1) 483 { 484 int v; 485 scanf("%d", &v); 486 --v; 487 processQuery(v); 488 } 489 } 490 } 491 ```