1133.md (7289B)
1 Source: https://codeforces.com/blog/entry/65807 2 3 [1133A - Middle of the Contest](/contest/1133/problem/A "Codeforces Round 544 (Div. 3)") 4 5 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 6 7 **Tutorial** 8 9 Tutorial is loading... 10 11 **Solution** 12 13 ``` 14 #include <bits/stdc++.h> 15 16 using namespace std; 17 18 int main() { 19 #ifdef _DEBUG 20 freopen("input.txt", "r", stdin); 21 // freopen("output.txt", "w", stdout); 22 #endif 23 24 int h1, m1; 25 scanf("%d:%d", &h1, &m1); 26 int h2, m2; 27 scanf("%d:%d", &h2, &m2); 28 int t1 = h1 * 60 + m1; 29 int t2 = h2 * 60 + m2; 30 int t3 = (t1 + t2) / 2; 31 printf("%02d:%02d\n", t3 / 60, t3 % 60); 32 33 return 0; 34 } 35 ``` 36 37 [1133B - Preparation for International Women's Day](/contest/1133/problem/B "Codeforces Round 544 (Div. 3)") 38 39 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 40 41 **Tutorial** 42 43 Tutorial is loading... 44 45 **Solution** 46 47 ``` 48 #include <bits/stdc++.h> 49 50 using namespace std; 51 52 int main() { 53 #ifdef _DEBUG 54 freopen("input.txt", "r", stdin); 55 // freopen("output.txt", "w", stdout); 56 #endif 57 58 int n, k; 59 cin >> n >> k; 60 vector<int> cnt(k); 61 for (int i = 0; i < n; ++i) { 62 int x; 63 cin >> x; 64 ++cnt[x % k]; 65 } 66 int ans = cnt[0] / 2; 67 if (k % 2 == 0) ans += cnt[k / 2] / 2; 68 for (int i = 1; i < (k + 1) / 2; ++i) { 69 int j = k - i; 70 ans += min(cnt[i], cnt[j]); 71 } 72 73 cout << ans * 2 << endl; 74 75 return 0; 76 } 77 ``` 78 79 [1133C - Balanced Team](/contest/1133/problem/C "Codeforces Round 544 (Div. 3)") 80 81 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 82 83 **Tutorial** 84 85 Tutorial is loading... 86 87 **Solution** 88 89 ``` 90 #include <bits/stdc++.h> 91 92 using namespace std; 93 94 int main() { 95 #ifdef _DEBUG 96 freopen("input.txt", "r", stdin); 97 // freopen("output.txt", "w", stdout); 98 #endif 99 100 int n; 101 cin >> n; 102 vector<int> a(n); 103 for (int i = 0; i < n; ++i) { 104 cin >> a[i]; 105 } 106 sort(a.begin(), a.end()); 107 int ans = 0; 108 int j = 0; 109 for (int i = 0; i < n; ++i) { 110 while (j < n && a[j] - a[i] <= 5) { 111 ++j; 112 ans = max(ans, j - i); 113 } 114 } 115 116 cout << ans << endl; 117 118 return 0; 119 } 120 ``` 121 122 [1133D - Zero Quantity Maximization](/contest/1133/problem/D "Codeforces Round 544 (Div. 3)") 123 124 Idea: [BledDest](/profile/BledDest "Grandmaster BledDest") 125 126 **Tutorial** 127 128 Tutorial is loading... 129 130 **Solution** 131 132 ``` 133 #include<bits/stdc++.h> 134 135 using namespace std; 136 137 #define x first 138 #define y second 139 140 const int N = 200043; 141 142 void norm(pair<int, int>& p) 143 { 144 if(p.x < 0) 145 { 146 p.x *= -1; 147 p.y *= -1; 148 } 149 else if (p.x == 0 && p.y < 0) 150 { 151 p.y *= -1; 152 } 153 int d = __gcd(abs(p.x), abs(p.y)); 154 p.x /= d; 155 p.y /= d; 156 } 157 158 map<pair<int, int>, int> m; 159 160 int a[N]; 161 int b[N]; 162 int n; 163 164 int main() 165 { 166 scanf("%d", &n); 167 for(int i = 0; i < n; i++) 168 scanf("%d", &a[i]); 169 for(int i = 0; i < n; i++) 170 scanf("%d", &b[i]); 171 int ans = 0; 172 int cnt0 = 0; 173 for(int i = 0; i < n; i++) 174 { 175 if(a[i] == 0) 176 { 177 if(b[i] == 0) 178 cnt0++; 179 } 180 else 181 { 182 pair<int, int> p = make_pair(-b[i], a[i]); 183 norm(p); 184 m[p]++; 185 ans = max(ans, m[p]); 186 } 187 } 188 cout << cnt0 + ans << endl; 189 } 190 ``` 191 192 [1133E - K Balanced Teams](/contest/1133/problem/E "Codeforces Round 544 (Div. 3)") 193 194 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 195 196 **Tutorial** 197 198 Tutorial is loading... 199 200 **Solution** 201 202 ``` 203 #include <bits/stdc++.h> 204 205 using namespace std; 206 207 int main() { 208 #ifdef _DEBUG 209 freopen("input.txt", "r", stdin); 210 // freopen("output.txt", "w", stdout); 211 #endif 212 213 int n, k; 214 cin >> n >> k; 215 vector<int> a(n); 216 for (int i = 0; i < n; ++i) { 217 cin >> a[i]; 218 } 219 sort(a.begin(), a.end()); 220 vector<int> cnt(n); 221 for (int i = 0; i < n; ++i) { 222 while (i + cnt[i] < n && a[i + cnt[i]] - a[i] <= 5) { 223 ++cnt[i]; 224 } 225 } 226 227 vector<vector<int>> dp(n + 1, vector<int>(k + 1)); 228 for (int i = 0; i < n; ++i) { 229 for (int j = 0; j <= k; ++j) { 230 dp[i + 1][j] = max(dp[i + 1][j], dp[i][j]); 231 if (j + 1 <= k) { 232 dp[i + cnt[i]][j + 1] = max(dp[i + cnt[i]][j + 1], dp[i][j] + cnt[i]); 233 } 234 } 235 } 236 237 cout << dp[n][k] << endl; 238 239 return 0; 240 } 241 ``` 242 243 [1133F1 - Spanning Tree with Maximum Degree](/contest/1133/problem/F1 "Codeforces Round 544 (Div. 3)") 244 245 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 246 247 **Tutorial** 248 249 Tutorial is loading... 250 251 **Solution** 252 253 ``` 254 #include <bits/stdc++.h> 255 256 using namespace std; 257 258 int n, m; 259 vector<vector<int>> g; 260 vector<int> deg, used; 261 vector<pair<int, int>> ans; 262 263 mt19937 rnd(time(NULL)); 264 265 void bfs(int s) { 266 used = vector<int>(n); 267 used[s] = 1; 268 queue<int> q; 269 q.push(s); 270 271 while (!q.empty()) { 272 int v = q.front(); 273 q.pop(); 274 for (auto to : g[v]) { 275 if (used[to]) continue; 276 if (rnd() & 1) ans.push_back(make_pair(v, to)); 277 else ans.push_back(make_pair(to, v)); 278 used[to] = 1; 279 q.push(to); 280 } 281 } 282 } 283 284 int main() { 285 #ifdef _DEBUG 286 freopen("input.txt", "r", stdin); 287 // freopen("output.txt", "w", stdout); 288 #endif 289 290 cin >> n >> m; 291 g = vector<vector<int>>(n); 292 deg = vector<int>(n); 293 for (int i = 0; i < m; ++i) { 294 int x, y; 295 cin >> x >> y; 296 --x, --y; 297 g[x].push_back(y); 298 g[y].push_back(x); 299 ++deg[x]; 300 ++deg[y]; 301 } 302 303 int pos = 0; 304 for (int i = 0; i < n; ++i) { 305 if (deg[pos] < deg[i]) { 306 pos = i; 307 } 308 } 309 310 bfs(pos); 311 shuffle(ans.begin(), ans.end(), rnd); 312 for (auto it : ans) cout << it.first + 1 << " " << it.second + 1 << endl; 313 314 return 0; 315 } 316 ``` 317 318 [1133F2 - Spanning Tree with One Fixed Degree](/contest/1133/problem/F2 "Codeforces Round 544 (Div. 3)") 319 320 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 321 322 **Tutorial** 323 324 Tutorial is loading... 325 326 **Solution** 327 328 ``` 329 #include <bits/stdc++.h> 330 331 using namespace std; 332 333 int n, m, D; 334 vector<vector<int>> g; 335 336 int cnt; 337 vector<int> p, color; 338 vector<pair<int, int>> ans; 339 340 mt19937 rnd(time(NULL)); 341 342 void bfs(int s, int bad) { 343 queue<int> q; 344 q.push(s); 345 color[s] = cnt; 346 while (!q.empty()) { 347 int v = q.front(); 348 q.pop(); 349 if (p[v] != -1) { 350 if (rnd() & 1) ans.push_back(make_pair(p[v], v)); 351 else ans.push_back(make_pair(v, p[v])); 352 } 353 for (auto to : g[v]) { 354 if (to == bad || color[to] != -1) continue; 355 p[to] = v; 356 color[to] = cnt; 357 q.push(to); 358 } 359 } 360 ++cnt; 361 } 362 363 int main() { 364 #ifdef _DEBUG 365 freopen("input.txt", "r", stdin); 366 // freopen("output.txt", "w", stdout); 367 #endif 368 369 cin >> n >> m >> D; 370 g = vector<vector<int>>(n); 371 for (int i = 0; i < m; ++i) { 372 int x, y; 373 cin >> x >> y; 374 --x, --y; 375 g[x].push_back(y); 376 g[y].push_back(x); 377 } 378 379 p = color = vector<int>(n, -1); 380 cnt = 0; 381 for (int i = 1; i < n; ++i) { 382 if (color[i] == -1) { 383 bfs(i, 0); 384 } 385 } 386 387 if (cnt > D || D > int(g[0].size())) { 388 cout << "NO" << endl; 389 return 0; 390 } 391 392 sort(g[0].begin(), g[0].end(), [](int a, int b) { 393 return color[a] < color[b]; 394 }); 395 396 for (int i = 0; i < int(g[0].size()); ++i) { 397 if (i == 0 || color[g[0][i]] != color[g[0][i - 1]]) { 398 ans.push_back(make_pair(0, g[0][i])); 399 } 400 } 401 D -= cnt; 402 for (int i = 1; i < int(g[0].size()); ++i) { 403 if (D == 0) break; 404 if (color[g[0][i]] == color[g[0][i - 1]]) { 405 ans.push_back(make_pair(0, g[0][i])); 406 --D; 407 } 408 } 409 410 g = vector<vector<int>>(n); 411 for (auto it : ans) { 412 g[it.first].push_back(it.second); 413 g[it.second].push_back(it.first); 414 } 415 ans.clear(); 416 p = color = vector<int>(n, -1); 417 cnt = 0; 418 bfs(0, -1); 419 420 shuffle(ans.begin(), ans.end(), rnd); 421 cout << "YES" << endl; 422 for (auto it : ans) { 423 cout << it.first + 1 << " " << it.second + 1 << endl; 424 } 425 426 return 0; 427 } 428 ```