1767.md (10073B)
1 Source: https://codeforces.com/blog/entry/110225 2 3 [1767A - Cut the Triangle](/contest/1767/problem/A "Educational Codeforces Round 140 (Rated for Div. 2)") 4 5 Idea: [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 input() 17 xs = [] 18 ys = [] 19 for j in range(3): 20 x, y = map(int, input().split()) 21 xs.append(x) 22 ys.append(y) 23 print('YES' if len(set(xs)) == 3 or len(set(ys)) == 3 else 'NO') 24 ``` 25 26 [1767B - Block Towers](/contest/1767/problem/B "Educational Codeforces Round 140 (Rated for Div. 2)") 27 28 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 29 30 **Tutorial** 31 32 Tutorial is loading... 33 34 **Solution (awoo)** 35 36 ``` 37 for _ in range(int(input())): 38 n = int(input()) 39 a = list(map(int, input().split())) 40 x = a[0] 41 a = sorted(a[1:]) 42 for y in a: 43 if y > x: 44 x += (y - x + 1) // 2 45 print(x) 46 ``` 47 48 [1767C - Count Binary Strings](/contest/1767/problem/C "Educational Codeforces Round 140 (Rated for Div. 2)") 49 50 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 51 52 **Tutorial** 53 54 Tutorial is loading... 55 56 **Solution (BledDest)** 57 58 ``` 59 #include<bits/stdc++.h> 60 61 using namespace std; 62 63 const int MOD = 998244353; 64 65 int add(int x, int y) 66 { 67 x += y; 68 while(x >= MOD) x -= MOD; 69 while(x < 0) x += MOD; 70 return x; 71 } 72 73 int mul(int x, int y) 74 { 75 return (x * 1ll * y) % MOD; 76 } 77 78 const int N = 143; 79 int n; 80 81 int a[N][N]; 82 int dp[N][N]; 83 84 bool check(int cnt, int last) 85 { 86 for(int i = 0; i < cnt; i++) 87 { 88 if(a[i][cnt - 1] == 0) continue; 89 if(a[i][cnt - 1] == 1 && last > i) return false; 90 if(a[i][cnt - 1] == 2 && last <= i) return false; 91 } 92 return true; 93 } 94 95 int main() 96 { 97 cin >> n; 98 for(int i = 0; i < n; i++) 99 { 100 for(int j = i; j < n; j++) 101 cin >> a[i][j]; 102 } 103 if(a[0][0] != 2) dp[1][0] = 2; 104 for(int i = 1; i < n; i++) 105 for(int j = 0; j < i; j++) 106 for(int k : vector<int>({j, i})) 107 if(check(i + 1, k)) 108 dp[i + 1][k] = add(dp[i + 1][k], dp[i][j]); 109 int ans = 0; 110 for(int i = 0; i < n; i++) 111 ans = add(ans, dp[n][i]); 112 cout << ans << endl; 113 } 114 ``` 115 116 [1767D - Playoff](/contest/1767/problem/D "Educational Codeforces Round 140 (Rated for Div. 2)") 117 118 Idea: [Neon](/profile/Neon "Candidate Master Neon") 119 120 **Tutorial** 121 122 Tutorial is loading... 123 124 **Solution (Neon)** 125 126 ``` 127 #include <bits/stdc++.h> 128 129 using namespace std; 130 131 int main() { 132 int n; 133 string s; 134 cin >> n >> s; 135 int k = count(s.begin(), s.end(), '1'); 136 for (int x = 1 << k; x <= (1 << n) - (1 << (n - k)) + 1; ++x) 137 cout << x << ' '; 138 } 139 ``` 140 141 [1767E - Algebra Flash](/contest/1767/problem/E "Educational Codeforces Round 140 (Rated for Div. 2)") 142 143 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 144 145 **Tutorial** 146 147 Tutorial is loading... 148 149 **Solution (awoo)** 150 151 ``` 152 #include <bits/stdc++.h> 153 154 #define forn(i, n) for (int i = 0; i < int(n); i++) 155 156 using namespace std; 157 158 int main() { 159 int n, m; 160 scanf("%d%d", &n, &m); 161 vector<int> c(n); 162 forn(i, n){ 163 scanf("%d", &c[i]); 164 --c[i]; 165 } 166 vector<int> x(m); 167 forn(i, m) scanf("%d", &x[i]); 168 169 vector<long long> g(m); 170 forn(i, n - 1){ 171 g[c[i]] |= 1ll << c[i + 1]; 172 g[c[i + 1]] |= 1ll << c[i]; 173 } 174 g[c[0]] |= 1ll << c[0]; 175 g[c[n - 1]] |= 1ll << c[n - 1]; 176 177 int mid = m / 2; 178 vector<int> dp(1 << mid, 1e9); 179 forn(mask, 1 << (m - mid)){ 180 long long chk = 0; 181 int tot = 0; 182 forn(i, m - mid){ 183 if ((mask >> i) & 1) 184 tot += x[i + mid]; 185 else 186 chk |= g[i + mid]; 187 } 188 if (((chk >> mid) | mask) != mask) 189 continue; 190 chk &= (1ll << mid) - 1; 191 dp[chk] = min(dp[chk], tot); 192 } 193 forn(i, mid) forn(mask, 1 << mid) if (!((mask >> i) & 1)){ 194 dp[mask | (1 << i)] = min(dp[mask | (1 << i)], dp[mask]); 195 } 196 int ans = 1e9; 197 forn(mask, 1 << mid){ 198 long long chk = 0; 199 int tot = 0; 200 forn(i, mid){ 201 if ((mask >> i) & 1) 202 tot += x[i]; 203 else 204 chk |= g[i]; 205 } 206 chk &= (1ll << mid) - 1; 207 if ((chk | mask) != mask) 208 continue; 209 ans = min(ans, dp[mask] + tot); 210 } 211 printf("%d\n", ans); 212 return 0; 213 } 214 ``` 215 216 [1767F - Two Subtrees](/contest/1767/problem/F "Educational Codeforces Round 140 (Rated for Div. 2)") 217 218 Idea: [shnirelman](/profile/shnirelman "Grandmaster shnirelman") 219 220 **Tutorial** 221 222 Tutorial is loading... 223 224 **Solution (shnirelman)** 225 226 ``` 227 #include <bits/stdc++.h> 228 229 #define f first 230 #define s second 231 232 using namespace std; 233 using li = long long; 234 using ld = long double; 235 using pii = pair<int, int>; 236 237 const int INF = 2e9 + 13; 238 const li INF64 = 2e18 + 13; 239 const int M = 998244353; 240 const int A = 2e5 + 13; 241 242 const int N = 2e5 + 13; 243 const int B = 2000; 244 const int SQRTA = 500; 245 const int K = N / B + 113; 246 247 int val[N]; 248 vector<int> g[N]; 249 int sz[N]; 250 int gr[N]; 251 int leaf[N], group_root[N]; 252 int par[N]; 253 bool heavy[N]; 254 255 int tin[N], tout[N], T = 0, mid[N]; 256 int et[N]; 257 int valet[N]; 258 259 void dfs1(int v, int pr, int depth) { 260 par[v] = pr; 261 sz[v] = 1; 262 263 int mx = -1; 264 for(int i = 0; i < g[v].size(); i++) { 265 int u = g[v][i]; 266 if(u != pr) { 267 dfs1(u, v, depth + 1); 268 sz[v] += sz[u]; 269 if(mx == -1 || sz[g[v][mx]] < sz[u]) 270 mx = i; 271 } 272 } 273 274 if(mx != -1) 275 swap(g[v][mx], g[v][0]); 276 } 277 278 void dfs2(int v) { 279 et[T] = v; 280 tin[v] = T++; 281 282 for(int u : g[v]) { 283 if(u != par[v]) 284 dfs2(u); 285 } 286 287 tout[v] = T; 288 } 289 290 struct Query { 291 int ind; 292 int v, u; 293 int lv, rv, lu, ru; 294 int b; 295 296 Query() {}; 297 }; 298 299 bool cmp(const Query& a, const Query& b) { 300 if(a.b != b.b) 301 return a.b < b.b; 302 else 303 return a.lu < b.lu; 304 } 305 306 int cnt[A]; 307 int block_index[A]; 308 int block_mx[A]; 309 int block_cnt_of_cnt[A / SQRTA + 13][A]; 310 311 inline void insert(int i) { 312 block_cnt_of_cnt[block_index[valet[i]]][cnt[valet[i]]]--; 313 cnt[valet[i]]++; 314 block_cnt_of_cnt[block_index[valet[i]]][cnt[valet[i]]]++; 315 if(cnt[valet[i]] > block_mx[block_index[valet[i]]]) 316 block_mx[block_index[valet[i]]]++; 317 } 318 319 inline void erase(int i) { 320 if(cnt[valet[i]] == block_mx[block_index[valet[i]]] && block_cnt_of_cnt[block_index[valet[i]]][cnt[valet[i]]] == 1) 321 block_mx[block_index[valet[i]]]--; 322 block_cnt_of_cnt[block_index[valet[i]]][cnt[valet[i]]]--; 323 cnt[valet[i]]--; 324 block_cnt_of_cnt[block_index[valet[i]]][cnt[valet[i]]]++; 325 } 326 327 int get_mode() { 328 int mx = 0; 329 for(int i = 0; i < A / SQRTA + 1; i++) 330 mx = max(mx, block_mx[i]); 331 for(int i = 0; ; i++) { 332 if(block_mx[i] == mx) { 333 for(int j = i * SQRTA; ; j++) { 334 if(cnt[j] == mx) 335 return j; 336 } 337 } 338 } 339 } 340 341 Query queries[N]; 342 int ans[N]; 343 344 void solve() { 345 int n; 346 cin >> n; 347 348 for(int i = 0; i < n; i++) 349 cin >> val[i]; 350 351 for(int i = 1; i < n; i++) { 352 int v, u; 353 cin >> v >> u; 354 355 v--; 356 u--; 357 358 g[v].push_back(u); 359 g[u].push_back(v); 360 } 361 362 dfs1(0, -1, 0); 363 364 vector<pii> ord(n); 365 for(int i = 0; i < n; i++) { 366 ord[i] = {sz[i], i}; 367 gr[i] = -1; 368 } 369 370 sort(ord.begin(), ord.end()); 371 372 for(int i = 0; i < n; i++) { 373 if(sz[i] >= B) 374 heavy[i] = true; 375 } 376 377 int cur = 0; 378 for(int i = 0; i < n; i++) { 379 int v = ord[i].s; 380 if(sz[v] < B || gr[v] != -1) 381 continue; 382 383 leaf[cur] = v; 384 385 int u = v; 386 while(gr[u] == -1 && sz[u] - sz[v] < B) { 387 gr[u] = cur; 388 group_root[cur] = u; 389 u = par[u]; 390 } 391 392 cur++; 393 } 394 395 dfs2(0); 396 397 for(int i = 0; i < n; i++) { 398 if(sz[i] < B) { 399 gr[i] = cur + tin[i] / B; 400 } 401 } 402 403 for(int i = 0; i < n; i++) 404 valet[i] = val[et[i]]; 405 406 for(int i = 0; i < A; i++) { 407 block_index[i] = i / SQRTA; 408 } 409 410 int q; 411 cin >> q; 412 413 for(int i = 0; i < q; i++) { 414 queries[i].ind = i; 415 cin >> queries[i].v >> queries[i].u; 416 417 queries[i].v--; 418 queries[i].u--; 419 420 queries[i].lv = tin[queries[i].v]; 421 queries[i].rv = tout[queries[i].v]; 422 queries[i].lu = tin[queries[i].u]; 423 queries[i].ru = tout[queries[i].u]; 424 425 if(queries[i].lv > queries[i].lu) { 426 swap(queries[i].v, queries[i].u); 427 swap(queries[i].lv, queries[i].lu); 428 swap(queries[i].rv, queries[i].ru); 429 } 430 431 queries[i].b = gr[queries[i].v]; 432 } 433 434 sort(queries, queries + q, cmp); 435 436 int lv = 0, rv = 0, lu = 0, ru = 0; 437 li fir = 0, sec = 0; 438 439 int hs = 0; 440 for(int i = 0; i < q; i++) { 441 int qlv = queries[i].lv; 442 int qrv = queries[i].rv; 443 int qlu = queries[i].lu; 444 int qru = queries[i].ru; 445 446 fir += abs(lv - qlv) + abs(rv - qrv); 447 sec += abs(lu - qlu) + abs(ru - qru); 448 449 if(queries[i].b < cur) { 450 while(rv < qrv) 451 insert(rv++); 452 while(lv > qlv) 453 insert(--lv); 454 while(rv > qrv) 455 erase(--rv); 456 while(lv < qlv) 457 erase(lv++); 458 } else { 459 while(rv > lv) 460 erase(--rv); 461 lv = qlv; 462 rv = lv; 463 while(rv < qrv) 464 insert(rv++); 465 } 466 467 while(ru < qru) 468 insert(ru++); 469 while(lu > qlu) 470 insert(--lu); 471 while(ru > qru) 472 erase(--ru); 473 while(lu < qlu) 474 erase(lu++); 475 476 ans[queries[i].ind] = get_mode(); 477 } 478 479 for(int i = 0; i < q; i++) 480 cout << ans[i] << endl; 481 } 482 483 mt19937 rnd(1); 484 485 int main() { 486 ios::sync_with_stdio(0); 487 cin.tie(0); 488 // freopen("input.txt", "r", stdin); 489 490 solve(); 491 } 492 ```