1681.md (8926B)
1 Source: https://codeforces.com/blog/entry/103163 2 3 [1681A - Game with Cards](/contest/1681/problem/A "Educational Codeforces Round 129 (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 t = int(input()) 15 for i in range(t): 16 n = int(input()) 17 a = list(map(int, input().split())) 18 m = int(input()) 19 b = list(map(int, input().split())) 20 21 print('Alice' if max(a) >= max(b) else 'Bob') 22 print('Alice' if max(a) > max(b) else 'Bob') 23 ``` 24 25 [1681B - Card Trick](/contest/1681/problem/B "Educational Codeforces Round 129 (Rated for Div. 2)") 26 27 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 28 29 **Tutorial** 30 31 Tutorial is loading... 32 33 **Solution (awoo)** 34 35 ``` 36 for _ in range(int(input())): 37 n = int(input()) 38 a = list(map(int, input().split())) 39 m = int(input()) 40 print(a[sum(map(int, input().split())) % n]) 41 ``` 42 43 [1681C - Double Sort](/contest/1681/problem/C "Educational Codeforces Round 129 (Rated for Div. 2)") 44 45 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 46 47 **Tutorial** 48 49 Tutorial is loading... 50 51 **Solution (awoo)** 52 53 ``` 54 for _ in range(int(input())): 55 n = int(input()) 56 a = list(map(int, input().split())) 57 b = list(map(int, input().split())) 58 tmp = [i for i in range(n)] 59 tmp.sort(key=lambda i: [a[i], b[i]]) 60 for i in range(n - 1): 61 if a[tmp[i]] > a[tmp[i + 1]] or b[tmp[i]] > b[tmp[i + 1]]: 62 print("-1") 63 break 64 else: 65 ans = [] 66 for i in range(n - 1): 67 for j in range(n - 1): 68 if a[j] > a[j + 1] or b[j] > b[j + 1]: 69 a[j], a[j + 1] = a[j + 1], a[j] 70 b[j], b[j + 1] = b[j + 1], b[j] 71 ans.append([j + 1, j + 2]) 72 print(len(ans)) 73 for it in ans: 74 print(*it) 75 ``` 76 77 [1681D - Required Length](/contest/1681/problem/D "Educational Codeforces Round 129 (Rated for Div. 2)") 78 79 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 80 81 **Tutorial** 82 83 Tutorial is loading... 84 85 **Solution (BledDest)** 86 87 ``` 88 #include<bits/stdc++.h> 89 90 using namespace std; 91 92 int main() 93 { 94 int n; 95 cin >> n; 96 long long v; 97 cin >> v; 98 queue<long long> q; 99 map<long long, int> dist; 100 dist[v] = 0; 101 q.push(v); 102 while(!q.empty()) 103 { 104 long long k = q.front(); 105 q.pop(); 106 string s = to_string(k); 107 if(s.size() == n) 108 { 109 cout << dist[k] << endl; 110 return 0; 111 } 112 for(auto x : s) 113 { 114 if(x == '0') continue; 115 long long w = k * int(x - '0'); 116 if(!dist.count(w)) 117 { 118 dist[w] = dist[k] + 1; 119 q.push(w); 120 } 121 } 122 } 123 cout << -1 << endl; 124 return 0; 125 } 126 ``` 127 128 [1681E - Labyrinth Adventures](/contest/1681/problem/E "Educational Codeforces Round 129 (Rated for Div. 2)") 129 130 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 131 132 **Tutorial** 133 134 Tutorial is loading... 135 136 **Solution (awoo)** 137 138 ``` 139 #include <bits/stdc++.h> 140 141 #define forn(i, n) for (int i = 0; i < int(n); i++) 142 143 using namespace std; 144 145 const long long INF64 = 1e18; 146 147 typedef pair<int, int> pt; 148 #define x first 149 #define y second 150 151 int main() { 152 int n; 153 scanf("%d", &n); 154 vector<vector<pt>> d(n - 1, vector<pt>(2)); 155 forn(i, n - 1) forn(j, 2){ 156 scanf("%d%d", &d[i][j].x, &d[i][j].y); 157 --d[i][j].x, --d[i][j].y; 158 } 159 int lg = 1; 160 while ((1 << lg) < n - 1) ++lg; 161 vector<vector<vector<vector<long long>>>> dp(n - 2, vector<vector<vector<long long>>>(lg, vector<vector<long long>>(2, vector<long long>(2, INF64)))); 162 forn(i, n - 2) forn(k, 2){ 163 dp[i][0][0][k] = abs(d[i][0].x + 1 - d[i + 1][k].x) + abs(d[i][0].y - d[i + 1][k].y) + 1; 164 dp[i][0][1][k] = abs(d[i][1].x - d[i + 1][k].x) + abs(d[i][1].y + 1 - d[i + 1][k].y) + 1; 165 } 166 for (int l = 1; l < lg; ++l) forn(i, n - 2) forn(j, 2) forn(k, 2) forn(t, 2) if (i + (1 << (l - 1)) < n - 2){ 167 dp[i][l][j][k] = min(dp[i][l][j][k], dp[i][l - 1][j][t] + dp[i + (1 << (l - 1))][l - 1][t][k]); 168 } 169 int m; 170 scanf("%d", &m); 171 forn(_, m){ 172 int x1, y1, x2, y2; 173 scanf("%d%d%d%d", &x1, &y1, &x2, &y2); 174 --x1, --y1, --x2, --y2; 175 int l1 = max(x1, y1), l2 = max(x2, y2); 176 if (l1 > l2){ 177 swap(l1, l2); 178 swap(x1, x2); 179 swap(y1, y2); 180 } 181 if (l1 == l2){ 182 printf("%d\n", abs(x1 - x2) + abs(y1 - y2)); 183 continue; 184 } 185 vector<long long> ndp(2); 186 ndp[0] = abs(x1 - d[l1][0].x) + abs(y1 - d[l1][0].y); 187 ndp[1] = abs(x1 - d[l1][1].x) + abs(y1 - d[l1][1].y); 188 for (int i = lg - 1; i >= 0; --i) if (l1 + (1 << i) < l2){ 189 vector<long long> tmp(2, INF64); 190 forn(j, 2) forn(k, 2) 191 tmp[k] = min(tmp[k], ndp[j] + dp[l1][i][j][k]); 192 ndp = tmp; 193 l1 += (1 << i); 194 } 195 long long ans = INF64; 196 ans = min(ans, ndp[0] + abs(d[l1][0].x + 1 - x2) + abs(d[l1][0].y - y2) + 1); 197 ans = min(ans, ndp[1] + abs(d[l1][1].x - x2) + abs(d[l1][1].y + 1 - y2) + 1); 198 printf("%lld\n", ans); 199 } 200 return 0; 201 } 202 ``` 203 204 [1681F - Unique Occurrences](/contest/1681/problem/F "Educational Codeforces Round 129 (Rated for Div. 2)") 205 206 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 207 208 **Tutorial** 209 210 Tutorial is loading... 211 212 **Solution 1 (awoo)** 213 214 ``` 215 #include <bits/stdc++.h> 216 217 #define forn(i, n) for (int i = 0; i < int(n); i++) 218 219 using namespace std; 220 221 struct edge{ 222 int u, w; 223 }; 224 225 int n; 226 vector<vector<edge>> g; 227 vector<vector<int>> ng; 228 vector<int> tin, tout, siz, ord; 229 int T; 230 231 vector<int> pw; 232 233 void init(int v, int p = -1){ 234 tin[v] = T++; 235 ord.push_back(v); 236 siz[v] = 1; 237 for (const auto &it : g[v]){ 238 int u = it.u, w = it.w; 239 if (u == p) continue; 240 pw[u] = w; 241 init(u, v); 242 siz[v] += siz[u]; 243 } 244 tout[v] = T; 245 } 246 247 int isp(int v, int u){ 248 return tin[v] <= tin[u] && tout[v] >= tout[u]; 249 } 250 251 vector<int> nsiz; 252 vector<vector<int>> dp; 253 254 long long dfs(int v, int x){ 255 long long res = 0; 256 for (int u : ng[v]) 257 res += dfs(u, x); 258 dp[v][0] = siz[v]; 259 dp[v][1] = 0; 260 for (int u : ng[v]) dp[v][0] -= siz[u]; 261 for (int u : ng[v]){ 262 if (pw[u] == x){ 263 res += dp[u][0] * 1ll * dp[v][0]; 264 dp[v][1] += dp[u][0]; 265 } 266 else{ 267 res += dp[u][0] * 1ll * dp[v][1]; 268 res += dp[u][1] * 1ll * dp[v][0]; 269 dp[v][0] += dp[u][0]; 270 dp[v][1] += dp[u][1]; 271 } 272 } 273 return res; 274 } 275 276 int main() { 277 scanf("%d", &n); 278 279 g.resize(n); 280 forn(i, n - 1){ 281 int v, u, w; 282 scanf("%d%d%d", &v, &u, &w); 283 --v, --u, --w; 284 g[v].push_back({u, w}); 285 g[u].push_back({v, w}); 286 } 287 288 T = 0; 289 tin.resize(n); 290 tout.resize(n); 291 siz.resize(n); 292 pw.resize(n, -1); 293 init(0); 294 295 vector<vector<int>> sv(n, vector<int>(1, 0)); 296 for (int v : ord) for (auto it : g[v]) 297 sv[it.w].push_back(v); 298 299 ng.resize(n); 300 nsiz.resize(n); 301 dp.resize(n, vector<int>(2)); 302 long long ans = 0; 303 forn(i, n) if (!sv[i].empty()){ 304 sv[i].resize(unique(sv[i].begin(), sv[i].end()) - sv[i].begin()); 305 vector<int> st; 306 for (int v : sv[i]){ 307 while (!st.empty() && !isp(st.back(), v)) 308 st.pop_back(); 309 if (!st.empty()) 310 ng[st.back()].push_back(v); 311 st.push_back(v); 312 } 313 ans += dfs(0, i); 314 315 for (int v : sv[i]) ng[v].clear(); 316 } 317 318 printf("%lld\n", ans); 319 return 0; 320 } 321 ``` 322 323 **Solution 2 (awoo)** 324 325 ``` 326 #include <bits/stdc++.h> 327 328 #define forn(i, n) for (int i = 0; i < int(n); i++) 329 330 using namespace std; 331 332 struct edge{ 333 int v, u, w; 334 }; 335 336 vector<vector<edge>> t; 337 338 void add(int v, int l, int r, int L, int R, const edge &e){ 339 if (L >= R) 340 return; 341 if (l == L && r == R){ 342 t[v].push_back(e); 343 return; 344 } 345 int m = (l + r) / 2; 346 add(v * 2, l, m, L, min(m, R), e); 347 add(v * 2 + 1, m, r, max(m, L), R, e); 348 } 349 350 vector<int> rk, p; 351 vector<int*> where; 352 vector<int> val; 353 354 int getp(int a){ 355 return a == p[a] ? a : getp(p[a]); 356 } 357 358 void unite(int a, int b){ 359 a = getp(a), b = getp(b); 360 if (a == b) return; 361 if (rk[a] < rk[b]) swap(a, b); 362 where.push_back(&rk[a]); 363 val.push_back(rk[a]); 364 rk[a] += rk[b]; 365 where.push_back(&p[b]); 366 val.push_back(p[b]); 367 p[b] = a; 368 } 369 370 void rollback(){ 371 *where.back() = val.back(); 372 where.pop_back(); 373 val.pop_back(); 374 } 375 376 long long trav(int v, int l, int r){ 377 int sv = where.size(); 378 for (auto it : t[v]) if (it.w == 0) 379 unite(it.v, it.u); 380 long long res = 0; 381 if (l == r - 1){ 382 for (auto it : t[v]) if (it.w == 1) 383 res += rk[getp(it.v)] * 1ll * rk[getp(it.u)]; 384 } 385 else{ 386 int m = (l + r) / 2; 387 res += trav(v * 2, l, m); 388 res += trav(v * 2 + 1, m, r); 389 } 390 while (int(where.size()) > sv) rollback(); 391 return res; 392 } 393 394 int main() { 395 int n; 396 scanf("%d", &n); 397 vector<edge> e(n - 1); 398 forn(i, n - 1){ 399 scanf("%d%d%d", &e[i].v, &e[i].u, &e[i].w); 400 --e[i].v, --e[i].u, --e[i].w; 401 } 402 sort(e.begin(), e.end(), [](const edge &a, const edge &b){ 403 return a.w < b.w; 404 }); 405 t.resize(4 * n); 406 forn(i, n - 1){ 407 int pos = lower_bound(e.begin(), e.end(), e[i], [](const edge &a, const edge &b){ 408 return a.w < b.w; 409 }) - e.begin(); 410 add(1, 0, n, 0, pos, {e[i].v, e[i].u, 0}); 411 add(1, 0, n, pos, pos + 1, {e[i].v, e[i].u, 1}); 412 add(1, 0, n, pos + 1, n, {e[i].v, e[i].u, 0}); 413 } 414 rk.resize(n, 1); 415 p.resize(n); 416 iota(p.begin(), p.end(), 0); 417 printf("%lld\n", trav(1, 0, n)); 418 return 0; 419 } 420 ```