1092.md (7782B)
1 Source: https://codeforces.com/blog/entry/63961 2 3 [1092A - Uniform String](/contest/1092/problem/A "Codeforces Round 527 (Div. 3)") 4 5 **Tutorial** 6 7 Tutorial is loading... 8 9 **Solution** 10 11 ``` 12 #include <bits/stdc++.h> 13 14 using namespace std; 15 16 int main() { 17 #ifdef _DEBUG 18 freopen("input.txt", "r", stdin); 19 // freopen("output.txt", "w", stdout); 20 #endif 21 22 int t; 23 cin >> t; 24 for (int i = 0; i < t; ++i) { 25 int n, k; 26 cin >> n >> k; 27 for (int j = 0; j < n; ++j) { 28 cout << char('a' + j % k); 29 } 30 cout << endl; 31 } 32 33 return 0; 34 } 35 ``` 36 37 [1092B - Teams Forming](/contest/1092/problem/B "Codeforces Round 527 (Div. 3)") 38 39 **Tutorial** 40 41 Tutorial is loading... 42 43 **Solution** 44 45 ``` 46 #include <bits/stdc++.h> 47 48 using namespace std; 49 50 int main() { 51 #ifdef _DEBUG 52 freopen("input.txt", "r", stdin); 53 // freopen("output.txt", "w", stdout); 54 #endif 55 56 int n; 57 cin >> n; 58 vector<int> a(n); 59 for (int i = 0; i < n; ++i) { 60 cin >> a[i]; 61 } 62 63 sort(a.begin(), a.end()); 64 int res = 0; 65 for (int i = 0; i < n; i += 2) { 66 res += a[i + 1] - a[i]; 67 } 68 69 cout << res << endl; 70 71 return 0; 72 } 73 ``` 74 75 [1092C - Prefixes and Suffixes](/contest/1092/problem/C "Codeforces Round 527 (Div. 3)") 76 77 **Tutorial** 78 79 Tutorial is loading... 80 81 **Solution** 82 83 ``` 84 #include <bits/stdc++.h> 85 86 using namespace std; 87 88 int n; 89 vector<string> v; 90 91 string res; 92 93 bool check(const string &pref, const string &suf) { 94 string s = pref + suf.substr(n - 2); 95 multiset<string> vv, sPref, sSuf; 96 for (int i = 0; i < n - 1; ++i) { 97 sPref.insert(s.substr(0, n - i - 1)); 98 vv.insert(s.substr(0, n - i - 1)); 99 sSuf.insert(s.substr(i + 1)); 100 vv.insert(s.substr(i + 1)); 101 } 102 if (vv == multiset<string>(v.begin(), v.end())) { 103 for (int i = 0; i < 2 * n - 2; ++i) { 104 if (sPref.count(v[i])) { 105 res += 'P'; 106 sPref.erase(sPref.find(v[i])); 107 } else if (sSuf.count(v[i])) { 108 res += 'S'; 109 sSuf.erase(sSuf.find(v[i])); 110 } else { 111 assert(false); 112 } 113 } 114 return true; 115 } 116 return false; 117 } 118 119 int main() { 120 #ifdef _DEBUG 121 freopen("input.txt", "r", stdin); 122 // freopen("output.txt", "w", stdout); 123 #endif 124 125 cin >> n; 126 v = vector<string>(2 * n - 2); 127 vector<string> big; 128 for (int i = 0; i < 2 * n - 2; ++i) { 129 cin >> v[i]; 130 if (int(v[i].size()) == n - 1) { 131 big.push_back(v[i]); 132 } 133 } 134 135 if (check(big[0], big[1])) { 136 cout << res << endl; 137 } else { 138 check(big[1], big[0]); 139 cout << res << endl; 140 } 141 142 return 0; 143 } 144 ``` 145 146 [1092D1 - Great Vova Wall (Version 1)](/contest/1092/problem/D1 "Codeforces Round 527 (Div. 3)") 147 148 **Tutorial** 149 150 Tutorial is loading... 151 152 **Solution 1** 153 154 ``` 155 #include <bits/stdc++.h> 156 157 #define forn(i, n) for (int i = 0; i < int(n); i++) 158 159 using namespace std; 160 161 const int N = 200 * 1000 + 13; 162 163 int n; 164 int a[N]; 165 166 int main() { 167 scanf("%d", &n); 168 forn(i, n){ 169 scanf("%d", &a[i]); 170 a[i] &= 1; 171 } 172 173 vector<int> st; 174 forn(i, n){ 175 if (!st.empty() && a[i] == st.back()) 176 st.pop_back(); 177 else 178 st.push_back(a[i]); 179 } 180 181 puts(st.size() <= 1 ? "YES" : "NO"); 182 return 0; 183 } 184 ``` 185 186 **Solution 2** 187 188 ``` 189 #include <bits/stdc++.h> 190 191 #define forn(i, n) for (int i = 0; i < int(n); i++) 192 193 using namespace std; 194 195 const int N = 200 * 1000 + 13; 196 197 int n; 198 int a[N]; 199 200 int main() { 201 scanf("%d", &n); 202 forn(i, n){ 203 scanf("%d", &a[i]); 204 a[i] &= 1; 205 } 206 207 set<pair<int, int>> seg, even; 208 forn(i, n){ 209 int j = i; 210 while (j + 1 < n && a[j + 1] == a[i]) ++j; 211 seg.insert({i, j}); 212 if ((j - i + 1) % 2 == 0) 213 even.insert({i, j}); 214 i = j; 215 } 216 217 while (seg.size() > 1 && !even.empty()){ 218 auto cur = *even.begin(); 219 even.erase(cur); 220 seg.erase(cur); 221 auto it = seg.lower_bound(cur); 222 if (it != seg.end()){ 223 cur.second = it->second; 224 if ((it->second - it->first + 1) % 2 == 0) 225 even.erase(*it); 226 seg.erase(it); 227 } 228 it = seg.lower_bound(cur); 229 if (it != seg.begin()){ 230 --it; 231 cur.first = it->first; 232 if ((it->second - it->first + 1) % 2 == 0) 233 even.erase(*it); 234 seg.erase(it); 235 } 236 seg.insert(cur); 237 if ((cur.second - cur.first + 1) % 2 == 0) 238 even.insert(cur); 239 } 240 241 puts(seg.size() == 1 ? "YES" : "NO"); 242 return 0; 243 } 244 ``` 245 246 [1092D2 - Great Vova Wall (Version 2)](/contest/1092/problem/D2 "Codeforces Round 527 (Div. 3)") 247 248 **Tutorial** 249 250 Tutorial is loading... 251 252 **Solution** 253 254 ``` 255 #include <bits/stdc++.h> 256 257 #define forn(i, n) for (int i = 0; i < int(n); i++) 258 259 using namespace std; 260 261 const int N = 1000 * 1000 + 13; 262 263 int n; 264 int a[N]; 265 266 int main() { 267 scanf("%d", &n); 268 forn(i, n) scanf("%d", &a[i]); 269 vector<int> st; 270 271 int mx = *max_element(a, a + n); 272 273 forn(i, n){ 274 if (a[i] == mx) continue; 275 276 int j = i - 1; 277 while (j + 1 < n && a[j + 1] != mx){ 278 ++j; 279 if (!st.empty() && st.back() == a[j]){ 280 st.pop_back(); 281 } 282 else if (st.empty() || st.back() > a[j]){ 283 st.push_back(a[j]); 284 } 285 else{ 286 puts("NO"); 287 return 0; 288 } 289 } 290 291 if (!st.empty()){ 292 puts("NO"); 293 return 0; 294 } 295 296 i = j; 297 } 298 299 puts("YES"); 300 return 0; 301 } 302 ``` 303 304 [1092E - Minimal Diameter Forest](/contest/1092/problem/E "Codeforces Round 527 (Div. 3)") 305 306 **Tutorial** 307 308 Tutorial is loading... 309 310 **Solution** 311 312 ``` 313 #include <bits/stdc++.h> 314 315 #define forn(i, n) for (int i = 0; i < int(n); i++) 316 317 using namespace std; 318 319 const int N = 200 * 1000 + 13; 320 const int INF = 1000000000; 321 322 int n, m; 323 vector<int> g[N]; 324 325 int bfs(int x, int dist[N]){ 326 queue<int> q; 327 q.push(x); 328 dist[x] = 0; 329 int lst = -1; 330 while (!q.empty()){ 331 int v = q.front(); 332 q.pop(); 333 lst = v; 334 for (auto u : g[v]) if (dist[u] > dist[v] + 1){ 335 dist[u] = dist[v] + 1; 336 q.push(u); 337 } 338 } 339 return lst; 340 } 341 342 int distx[N], disty[N]; 343 bool used[N]; 344 vector<int> cur; 345 346 void dfs(int v){ 347 used[v] = true; 348 cur.push_back(v); 349 for (auto u : g[v]) if (!used[u]) 350 dfs(u); 351 } 352 353 int main() { 354 scanf("%d%d", &n, &m); 355 forn(i, m){ 356 int v, u; 357 scanf("%d%d", &v, &u); 358 --v, --u; 359 g[v].push_back(u); 360 g[u].push_back(v); 361 } 362 363 forn(i, n) distx[i] = disty[i] = INF; 364 365 vector<pair<int, int>> comps; 366 forn(i, n) if (!used[i]){ 367 cur.clear(); 368 dfs(i); 369 int x = bfs(i, distx); 370 int y = bfs(x, disty); 371 for (auto v : cur) distx[v] = INF; 372 bfs(y, distx); 373 int d = disty[y], center; 374 for (auto v : cur) if (distx[v] == d / 2 && disty[v] == d - d / 2) 375 center = v; 376 comps.push_back({d, center}); 377 } 378 379 vector<pair<int, int>> ans; 380 nth_element(comp.begin(), comp.end() - 1, comp.end()); 381 forn(i, int(comps.size()) - 1){ 382 g[comps[i].second].push_back(comps.back().second); 383 g[comps.back().second].push_back(comps[i].second); 384 ans.push_back({comps[i].second, comps.back().second}); 385 } 386 387 forn(i, n) distx[i] = disty[i] = INF; 388 int y = bfs(bfs(comps.back().second, distx), disty); 389 390 printf("%d\n", disty[y]); 391 for (auto it : ans) 392 printf("%d %d\n", it.first + 1, it.second + 1); 393 return 0; 394 } 395 ``` 396 397 [1092F - Tree with Maximum Cost](/contest/1092/problem/F "Codeforces Round 527 (Div. 3)") 398 399 **Tutorial** 400 401 Tutorial is loading... 402 403 **Solution** 404 405 ``` 406 #include <bits/stdc++.h> 407 408 using namespace std; 409 410 long long res, ans; 411 412 vector<int> a; 413 vector<long long> sum; 414 vector<vector<int>> g; 415 416 void dfs(int v, int p = -1, int h = 0) { 417 res += h * 1ll * a[v]; 418 sum[v] = a[v]; 419 420 for (auto to : g[v]) { 421 if (to == p) { 422 continue; 423 } 424 dfs(to, v, h + 1); 425 sum[v] += sum[to]; 426 } 427 } 428 429 void go(int v, int p = -1) { 430 ans = max(ans, res); 431 432 for (auto to : g[v]) { 433 if (to == p) { 434 continue; 435 } 436 437 res -= sum[to]; 438 sum[v] -= sum[to]; 439 res += sum[v]; 440 sum[to] += sum[v]; 441 442 go(to, v); 443 444 sum[to] -= sum[v]; 445 res -= sum[v]; 446 sum[v] += sum[to]; 447 res += sum[to]; 448 } 449 } 450 451 int main() { 452 #ifdef _DEBUG 453 freopen("input.txt", "r", stdin); 454 // freopen("output.txt", "w", stdout); 455 #endif 456 457 int n; 458 cin >> n; 459 a = vector<int>(n); 460 sum = vector<long long>(n); 461 g = vector<vector<int>>(n); 462 for (int i = 0; i < n; ++i) { 463 cin >> a[i]; 464 } 465 for (int i = 0; i < n - 1; ++i) { 466 int x, y; 467 cin >> x >> y; 468 --x, --y; 469 g[x].push_back(y); 470 g[y].push_back(x); 471 } 472 473 dfs(0); 474 go(0); 475 476 cout << ans << endl; 477 478 return 0; 479 } 480 ```