1494.md (9195B)
1 Source: https://codeforces.com/blog/entry/88344 2 3 [1494A - ABC String](/contest/1494/problem/A "Educational Codeforces Round 105 (Rated for Div. 2)") 4 5 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 6 7 **Tutorial** 8 9 Tutorial is loading... 10 11 **Solution (Neon)** 12 13 ``` 14 #include <bits/stdc++.h> 15 16 using namespace std; 17 18 bool solve() { 19 string s; 20 cin >> s; 21 vector<int> d(3); 22 int x = s[0] - 'A'; 23 int y = s.back() - 'A'; 24 if (x == y) 25 return false; 26 d[x] = 1; d[y] = -1; 27 if (count(s.begin(), s.end(), 'A' + x) == s.length() / 2) 28 d[3 ^ x ^ y] = -1; 29 else 30 d[3 ^ x ^ y] = 1; 31 int bal = 0; 32 for (char c : s) { 33 bal += d[c - 'A']; 34 if (bal < 0) return false; 35 } 36 return bal == 0; 37 } 38 39 int main() { 40 int t; cin >> t; 41 while (t--) { 42 cout << (solve() ? "YES\n" : "NO\n"); 43 } 44 } 45 ``` 46 47 [1494B - Berland Crossword](/contest/1494/problem/B "Educational Codeforces Round 105 (Rated for Div. 2)") 48 49 Idea: [Neon](/profile/Neon "Candidate Master Neon") 50 51 **Tutorial** 52 53 Tutorial is loading... 54 55 **Solution (awoo)** 56 57 ``` 58 for _ in range(int(input())): 59 n, U, R, D, L = map(int, input().split()) 60 for mask in range(16): 61 rU, rR, rD, rL = U, R, D, L 62 if mask & 1: 63 rU -= 1 64 rL -= 1 65 if mask & 2: 66 rL -= 1 67 rD -= 1 68 if mask & 4: 69 rD -= 1 70 rR -= 1 71 if mask & 8: 72 rR -= 1 73 rU -= 1 74 if min(rU, rR, rD, rL) >= 0 and max(rU, rR, rD, rL) <= n - 2: 75 print("YES") 76 break 77 else: 78 print("NO") 79 ``` 80 81 [1494C - 1D Sokoban](/contest/1494/problem/C "Educational Codeforces Round 105 (Rated for Div. 2)") 82 83 Idea: [adedalic](/profile/adedalic "International Master adedalic") 84 85 **Tutorial** 86 87 Tutorial is loading... 88 89 **Solution (awoo)** 90 91 ``` 92 #include <bits/stdc++.h> 93 94 #define forn(i, n) for (int i = 0; i < int(n); i++) 95 96 using namespace std; 97 98 int calc(const vector<int> &a, const vector<int> &b){ 99 int n = a.size(); 100 int m = b.size(); 101 vector<int> su(n + 1); 102 int r = m - 1; 103 for (int i = n - 1; i >= 0; --i){ 104 su[i] = su[i + 1]; 105 while (r >= 0 && b[r] > a[i]) --r; 106 if (r >= 0 && b[r] == a[i]) ++su[i]; 107 } 108 int ans = 0; 109 int j = 0; 110 r = 0; 111 forn(l, m){ 112 while (j < n && a[j] <= b[l] + j) ++j; 113 while (r < m && b[r] - b[l] < j) ++r; 114 ans = max(ans, r - l + su[j]); 115 } 116 return ans; 117 } 118 119 int main() { 120 int t; 121 scanf("%d", &t); 122 forn(_, t){ 123 int n, m; 124 scanf("%d%d", &n, &m); 125 vector<int> a(n), b(m); 126 forn(i, n) scanf("%d", &a[i]); 127 forn(i, m) scanf("%d", &b[i]); 128 vector<int> al, bl, ar, br; 129 forn(i, n){ 130 if (a[i] < 0) al.push_back(-a[i]); 131 else ar.push_back(a[i]); 132 } 133 forn(i, m){ 134 if (b[i] < 0) bl.push_back(-b[i]); 135 else br.push_back(b[i]); 136 } 137 reverse(al.begin(), al.end()); 138 reverse(bl.begin(), bl.end()); 139 printf("%d\n", calc(al, bl) + calc(ar, br)); 140 } 141 return 0; 142 } 143 ``` 144 145 [1494D - Dogeforces](/contest/1494/problem/D "Educational Codeforces Round 105 (Rated for Div. 2)") 146 147 Idea: [Neon](/profile/Neon "Candidate Master Neon") 148 149 **Tutorial** 150 151 Tutorial is loading... 152 153 **Solution (Neon)** 154 155 ``` 156 #include <bits/stdc++.h> 157 158 using namespace std; 159 160 #define sz(a) int((a).size()) 161 162 const int N = 505; 163 164 int n; 165 int a[N][N]; 166 int c[2 * N]; 167 vector<pair<int, int>> e; 168 169 int calc(vector<int> ls) { 170 if (sz(ls) == 1) 171 return ls[0]; 172 173 int res = -1; 174 for (int u : ls) 175 res = max(res, a[ls[0]][u]); 176 177 vector<vector<int>> ch; 178 ch.push_back({ls[0]}); 179 for (int i = 1; i < sz(ls); ++i) { 180 int v = ls[i]; 181 int group = -1; 182 for (int j = 0; j < sz(ch); ++j) { 183 if (a[v][ch[j][0]] != res) { 184 group = j; 185 break; 186 } 187 } 188 if (group == -1) { 189 group = sz(ch); 190 ch.push_back({}); 191 } 192 ch[group].push_back(v); 193 } 194 195 int v = n++; 196 c[v] = res; 197 for (int i = 0; i < sz(ch); ++i) { 198 int u = calc(ch[i]); 199 e.emplace_back(u, v); 200 } 201 return v; 202 } 203 204 int main() { 205 cin >> n; 206 for (int i = 0; i < n; ++i) 207 for (int j = 0; j < n; ++j) 208 cin >> a[i][j]; 209 for (int i = 0; i < n; ++i) 210 c[i] = a[i][i]; 211 vector<int> ls(n); 212 iota(ls.begin(), ls.end(), 0); 213 int root = calc(ls); 214 cout << n << '\n'; 215 for (int i = 0; i < n; ++i) 216 cout << c[i] << ' '; 217 cout << '\n' << root + 1 << '\n'; 218 for (auto it : e) 219 cout << it.first + 1 << ' ' << it.second + 1 << '\n'; 220 } 221 ``` 222 223 [1494E - A-Z Graph](/contest/1494/problem/E "Educational Codeforces Round 105 (Rated for Div. 2)") 224 225 Idea: [adedalic](/profile/adedalic "International Master adedalic") 226 227 **Tutorial** 228 229 Tutorial is loading... 230 231 **Solution (adedalic)** 232 233 ``` 234 #include<bits/stdc++.h> 235 236 using namespace std; 237 238 #define fore(i, l, r) for(int i = int(l); i < int(r); i++) 239 #define sz(a) int((a).size()) 240 241 #define x first 242 #define y second 243 244 typedef pair<int, int> pt; 245 246 int main() { 247 ios_base::sync_with_stdio(false); 248 cin.tie(NULL); 249 250 int n, m; 251 cin >> n >> m; 252 253 map<pt, int> allEdges; 254 set<pt> difPairs, eqPairs; 255 256 fore (q, 0, m) { 257 char tp; cin >> tp; 258 if (tp == '+') { 259 int u, v; 260 char c; 261 cin >> u >> v >> c; 262 263 if (allEdges.count({v, u})) { 264 if (allEdges[{v, u}] == c) 265 eqPairs.emplace(min(u, v), max(u, v)); 266 else 267 difPairs.emplace(min(u, v), max(u, v)); 268 } 269 allEdges[{u, v}] = c; 270 271 } else if (tp == '-') { 272 int u, v; 273 cin >> u >> v; 274 if (eqPairs.count({min(u, v), max(u, v)})) 275 eqPairs.erase({min(u, v), max(u, v)}); 276 if (difPairs.count({min(u, v), max(u, v)})) 277 difPairs.erase({min(u, v), max(u, v)}); 278 279 allEdges.erase({u, v}); 280 } else { 281 int k; 282 cin >> k; 283 284 bool hasAns = !eqPairs.empty(); 285 if (k & 1) 286 hasAns |= !difPairs.empty(); 287 cout << (hasAns ? "YES" : "NO") << '\n'; 288 } 289 } 290 291 return 0; 292 } 293 ``` 294 295 [1494F - Delete The Edges](/contest/1494/problem/F "Educational Codeforces Round 105 (Rated for Div. 2)") 296 297 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 298 299 **Tutorial** 300 301 Tutorial is loading... 302 303 **Solution (BledDest)** 304 305 ``` 306 #include <bits/stdc++.h> 307 308 using namespace std; 309 310 const int N = 300043; 311 312 int n, m; 313 set<int> g[N]; 314 set<int> g2[N]; 315 316 vector<int> res; 317 318 void euler(int x) 319 { 320 while(!g2[x].empty()) 321 { 322 int y = *g2[x].begin(); 323 g2[x].erase(y); 324 g2[y].erase(x); 325 euler(y); 326 } 327 res.push_back(x); 328 } 329 330 bool check(int c) 331 { 332 for(int i = 1; i <= n; i++) 333 g2[i] = g[i]; 334 res = vector<int>(); 335 euler(c); 336 int curm = 0; 337 for(int i = 1; i <= n; i++) 338 curm += g[i].size(); 339 for(int i = 1; i <= n; i++) 340 g2[i] = g[i]; 341 for(int i = 1; i < res.size(); i++) 342 { 343 int x = res[i - 1]; 344 int y = res[i]; 345 if(g2[x].count(y) != 1) 346 return false; 347 g2[x].erase(y); 348 g2[y].erase(x); 349 } 350 return curm / 2 + 1 == res.size(); 351 } 352 353 int main() 354 { 355 scanf("%d %d", &n, &m); 356 for(int i = 0; i < m; i++) 357 { 358 int x, y; 359 scanf("%d %d", &x, &y); 360 g[x].insert(y); 361 g[y].insert(x); 362 } 363 for(int i = 1; i <= n; i++) 364 { 365 set<int> pr = g[i]; 366 set<int> diff; 367 for(auto x : pr) 368 if(g[x].size() % 2 == 1) 369 { 370 g[i].erase(x); 371 g[x].erase(i); 372 diff.insert(x); 373 } 374 if(check(i)) 375 { 376 res.push_back(-1); 377 for(auto x : diff) 378 { 379 res.push_back(x); 380 res.push_back(i); 381 } 382 printf("%d\n", res.size()); 383 for(auto x : res) printf("%d ", x); 384 puts(""); 385 exit(0); 386 } 387 for(auto x : pr) 388 { 389 if(g[i].count(x)) 390 { 391 g[i].erase(x); 392 g[x].erase(i); 393 diff.insert(x); 394 } 395 else 396 { 397 g[i].insert(x); 398 g[x].insert(i); 399 diff.erase(x); 400 } 401 if(check(i)) 402 { 403 res.push_back(-1); 404 for(auto x : diff) 405 { 406 res.push_back(x); 407 res.push_back(i); 408 } 409 printf("%d\n", res.size()); 410 for(auto x : res) printf("%d ", x); 411 puts(""); 412 exit(0); 413 } 414 if(g[i].count(x)) 415 { 416 g[i].erase(x); 417 g[x].erase(i); 418 diff.insert(x); 419 } 420 else 421 { 422 g[i].insert(x); 423 g[x].insert(i); 424 diff.erase(x); 425 } 426 } 427 for(auto x : diff) 428 { 429 g[i].insert(x); 430 g[x].insert(i); 431 } 432 } 433 puts("0"); 434 } 435 ```