1721.md (8551B)
1 Source: https://codeforces.com/blog/entry/106416 2 3 [1721A - Image](/contest/1721/problem/A "Educational Codeforces Round 134 (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 #include<bits/stdc++.h> 15 16 using namespace std; 17 18 int main() 19 { 20 int t; 21 cin >> t; 22 for(int i = 0; i < t; i++) 23 { 24 string s1, s2; 25 cin >> s1 >> s2; 26 s1 += s2; 27 cout << set<char>(s1.begin(), s1.end()).size() - 1 << endl; 28 } 29 } 30 ``` 31 32 [1721B - Deadly Laser](/contest/1721/problem/B "Educational Codeforces Round 134 (Rated for Div. 2)") 33 34 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 35 36 **Tutorial** 37 38 Tutorial is loading... 39 40 **Solution (awoo)** 41 42 ``` 43 for _ in range(int(input())): 44 n, m, sx, sy, d = map(int, input().split()) 45 if min(sx - 1, m - sy) <= d and min(n - sx, sy - 1) <= d: 46 print(-1) 47 else: 48 print(n + m - 2) 49 ``` 50 51 [1721C - Min-Max Array Transformation](/contest/1721/problem/C "Educational Codeforces Round 134 (Rated for Div. 2)") 52 53 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 54 55 **Tutorial** 56 57 Tutorial is loading... 58 59 **Solution (adedalic)** 60 61 ``` 62 fun main() { 63 repeat(readLine()!!.toInt()) { 64 val n = readLine()!!.toInt() 65 val a = readLine()!!.split(' ').map { it.toInt() } 66 val b = readLine()!!.split(' ').map { it.toInt() } 67 68 val indices = (0 until n).sortedBy { a[it] } 69 val mn = Array(n) { 0 } 70 val mx = Array(n) { 0 } 71 72 var lst = n 73 for (i in n - 1 downTo 0) { 74 val pos = indices[i] 75 mn[pos] = lowerBound(b, a[pos]) 76 mx[pos] = lst - 1; 77 if (i == mn[pos]) 78 lst = i 79 80 mn[pos] = b[mn[pos]] - a[pos] 81 mx[pos] = b[mx[pos]] - a[pos] 82 } 83 println(mn.joinToString(" ")) 84 println(mx.joinToString(" ")) 85 } 86 } 87 88 fun lowerBound(a: List<Int>, v: Int): Int { 89 var l = -1; var r = a.size 90 while (r - l > 1) { 91 val m = (l + r) / 2 92 if (a[m] < v) 93 l = m 94 else 95 r = m 96 } 97 return r 98 } 99 ``` 100 101 [1721D - Maximum AND](/contest/1721/problem/D "Educational Codeforces Round 134 (Rated for Div. 2)") 102 103 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 104 105 **Tutorial** 106 107 Tutorial is loading... 108 109 **Solution (Neon)** 110 111 ``` 112 #include <bits/stdc++.h> 113 114 using namespace std; 115 116 int main() { 117 ios::sync_with_stdio(false); cin.tie(0); 118 int t; 119 cin >> t; 120 while (t--) { 121 int n; 122 cin >> n; 123 vector<int> a(n), b(n); 124 for (int& x : a) cin >> x; 125 for (int& x : b) cin >> x; 126 127 auto check = [&](int ans) { 128 map<int, int> cnt; 129 for (int x : a) ++cnt[x & ans]; 130 for (int x : b) --cnt[~x & ans]; 131 bool ok = true; 132 for (auto it : cnt) ok &= it.second == 0; 133 return ok; 134 }; 135 136 int ans = 0; 137 for (int bit = 29; bit >= 0; --bit) 138 if (check(ans | (1 << bit))) 139 ans |= 1 << bit; 140 141 cout << ans << '\n'; 142 } 143 } 144 ``` 145 146 [1721E - Prefix Function Queries](/contest/1721/problem/E "Educational Codeforces Round 134 (Rated for Div. 2)") 147 148 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 149 150 **Tutorial** 151 152 Tutorial is loading... 153 154 **Solution (awoo)** 155 156 ``` 157 #include <bits/stdc++.h> 158 159 #define forn(i, n) for (int i = 0; i < int(n); i++) 160 161 using namespace std; 162 163 const int AL = 26; 164 165 vector<int> prefix_function(const string &s){ 166 int n = s.size(); 167 vector<int> p(n); 168 for (int i = 1; i < n; ++i){ 169 int k = p[i - 1]; 170 while (k > 0 && s[i] != s[k]) 171 k = p[k - 1]; 172 k += (s[i] == s[k]); 173 p[i] = k; 174 } 175 return p; 176 } 177 178 int main() { 179 cin.tie(0); 180 iostream::sync_with_stdio(false); 181 string s; 182 cin >> s; 183 int n = s.size(); 184 auto p = prefix_function(s); 185 vector<vector<int>> A(n, vector<int>(AL)); 186 forn(i, n) forn(j, AL){ 187 if (i > 0 && j != s[i] - 'a') 188 A[i][j] = A[p[i - 1]][j]; 189 else 190 A[i][j] = i + (j == s[i] - 'a'); 191 } 192 int q; 193 cin >> q; 194 vector<vector<int>> ans(q); 195 forn(z, q){ 196 string t; 197 cin >> t; 198 int m = t.size(); 199 s += t; 200 for (int i = n; i < n + m; ++i){ 201 A.push_back(vector<int>(AL)); 202 forn(j, AL){ 203 if (j != s[i] - 'a') 204 A[i][j] = A[p[i - 1]][j]; 205 else 206 A[i][j] = i + (j == s[i] - 'a'); 207 } 208 p.push_back(A[p[i - 1]][s[i] - 'a']); 209 ans[z].push_back(p[i]); 210 } 211 forn(_, m){ 212 p.pop_back(); 213 s.pop_back(); 214 A.pop_back(); 215 } 216 } 217 for (auto &it : ans){ 218 for (int x : it) 219 cout << x << ' '; 220 cout << '\n'; 221 } 222 return 0; 223 } 224 ``` 225 226 [1721F - Matching Reduction](/contest/1721/problem/F "Educational Codeforces Round 134 (Rated for Div. 2)") 227 228 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 229 230 **Tutorial** 231 232 Tutorial is loading... 233 234 **Solution (BledDest)** 235 236 ``` 237 #include<bits/stdc++.h> 238 239 using namespace std; 240 241 const int N = 400043; 242 const int INF = int(1e9); 243 244 struct edge 245 { 246 int y, c, f; 247 edge() {}; 248 edge(int y, int c, int f) : y(y), c(c), f(f) {}; 249 }; 250 251 vector<edge> e; 252 vector<int> g[N]; 253 int S, T, V; 254 int d[N], lst[N]; 255 int n1, n2, m, q; 256 map<pair<int, int>, int> es; 257 258 void add_edge(int x, int y, int c) 259 { 260 g[x].push_back(e.size()); 261 e.push_back(edge(y, c, 0)); 262 g[y].push_back(e.size()); 263 e.push_back(edge(x, 0, 0)); 264 } 265 266 int rem(int x) 267 { 268 return e[x].c - e[x].f; 269 } 270 271 bool bfs() 272 { 273 for (int i = 0; i < V; i++) 274 d[i] = INF; 275 d[S] = 0; 276 queue<int> q; 277 q.push(S); 278 while (!q.empty()) 279 { 280 int k = q.front(); 281 q.pop(); 282 for (auto y : g[k]) 283 { 284 if (rem(y) == 0) 285 continue; 286 int to = e[y].y; 287 if (d[to] > d[k] + 1) 288 { 289 q.push(to); 290 d[to] = d[k] + 1; 291 } 292 } 293 } 294 return d[T] < INF; 295 } 296 297 int dfs(int x, int mx) 298 { 299 if (x == T || mx == 0) 300 return mx; 301 int sum = 0; 302 for (; lst[x] < g[x].size(); lst[x]++) 303 { 304 int num = g[x][lst[x]]; 305 int r = rem(num); 306 if (r == 0) 307 continue; 308 int to = e[num].y; 309 if (d[to] != d[x] + 1) 310 continue; 311 int pushed = dfs(to, min(r, mx)); 312 if (pushed > 0) 313 { 314 e[num].f += pushed; 315 e[num ^ 1].f -= pushed; 316 sum += pushed; 317 mx -= pushed; 318 if (mx == 0) 319 return sum; 320 } 321 } 322 return sum; 323 } 324 325 int Dinic() 326 { 327 int ans = 0; 328 while (bfs()) 329 { 330 for (int i = 0; i < V; i++) 331 lst[i] = 0; 332 int f = 0; 333 do 334 { 335 f = dfs(S, INF); 336 ans += f; 337 } while (f > 0); 338 } 339 return ans; 340 } 341 342 int main() 343 { 344 scanf("%d %d %d %d", &n1, &n2, &m, &q); 345 S = n1 + n2; 346 T = S + 1; 347 V = T + 1; 348 for (int i = 0; i < m; i++) 349 { 350 int x, y; 351 scanf("%d %d", &x, &y); 352 --x; 353 --y; 354 es[make_pair(x, y)] = i + 1; 355 add_edge(x, n1 + y, 1); 356 } 357 for (int i = 0; i < n1; i++) 358 add_edge(S, i, 1); 359 for (int i = 0; i < n2; i++) 360 add_edge(i + n1, T, 1); 361 Dinic(); 362 bfs(); 363 vector<int> vertex_cover; 364 map<int, int> index; 365 set<int> matched; 366 long long sum = 0; 367 for (int i = 0; i < n1; i++) 368 if (d[i] == INF) 369 { 370 vertex_cover.push_back(i + 1); 371 for (auto ei : g[i]) 372 if (e[ei].f == 1) 373 { 374 int idx = es[make_pair(i, e[ei].y - n1)]; 375 index[i + 1] = idx; 376 sum += idx; 377 matched.insert(idx); 378 } 379 } 380 for (int i = 0; i < n2; i++) 381 if (d[i + n1] != INF) 382 { 383 vertex_cover.push_back(-(i + 1)); 384 for (auto ei : g[i + n1]) 385 if (e[ei].f == -1) 386 { 387 int idx = es[make_pair(e[ei].y, i)]; 388 index[-(i + 1)] = idx; 389 sum += idx; 390 matched.insert(idx); 391 } 392 } 393 for (int i = 0; i < q; i++) 394 { 395 int s; 396 scanf("%d", &s); 397 if (s == 1) 398 { 399 puts("1"); 400 int v = vertex_cover.back(); 401 vertex_cover.pop_back(); 402 printf("%d\n", v); 403 sum -= index[v]; 404 matched.erase(index[v]); 405 printf("%lld\n", sum); 406 } 407 else 408 { 409 printf("%d\n", (int)matched.size()); 410 for(auto x : matched) printf("%d ", x); 411 puts(""); 412 } 413 fflush(stdout); 414 } 415 } 416 ```