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