1254.md (21269B)
1 Source: https://codeforces.com/blog/entry/71594 2 3 [1255A - Изменение громкости](/contest/1255/problem/A "Codeforces Round 601 (Div. 2)") 4 5 Author: [UncleGrandpa](/profile/UncleGrandpa "Мастер UncleGrandpa"). Prepared by [UncleGrandpa](/profile/UncleGrandpa "Мастер UncleGrandpa") 6 7 **Tutorial** 8 9 Tutorial is loading... 10 11 [1255B - Замки для холодильников](/contest/1255/problem/B "Codeforces Round 601 (Div. 2)") 12 13 Author: [I_love_tigersugar](/profile/I_love_tigersugar "Гроссмейстер I_love_tigersugar") ft. [MikeMirzayanov](/profile/MikeMirzayanov "Штаб, MikeMirzayanov"). Prepared by [UncleGrandpa](/profile/UncleGrandpa "Мастер UncleGrandpa") 14 15 **Tutorial** 16 17 #### Modelize the problem 18 19 We modelize the problem as graph, where each fridge is a vertex and each chain is an edge between two vertexes. The problem is now equivalent to: Given a graph with $n$ vertexes, each vertex has a value $a_i \ge 0$. We have to add $m$ edges to the graph such that each vertex is connected to at least two different vertexes and the total cost of edges added is minimum. The cost of an edge is the sum of value of its two end-points. 20 21 #### Observe some basic properties of graph 22 23 Now, each edge added will increase the sum of degree of all vertexes by 2. So adding m edges will make the sum of degree equal to $2 \times m$. Since each vertexes must be connected to at least $2$ other vertexes, the minimum sum of degree is $2 \times n$. 24 25 * Case 1: $2\times m \lt 2\times n \Leftrightarrow m \lt n$ 26 27 In this case, it is obvious that the answer is $-1$. 28 29 * Case 2: $2\times m = 2\times n \Leftrightarrow m=n$ 30 31 In this case, it is easy to see that the degree of each vertex will be exactly 2. As a result, no matter what edges we add, the result is still $2\times (a_1+a_2+...+a_n)$. But please take note that if $n=2$, then the answer will be $-1$ since for each vertex we have at most $1$ different vertex to connect to. 32 33 * Case 3(Of the original, pre-modified version of the problem): $2\times m \gt 2\times n \Leftrightarrow m \gt n$ 34 35 Please read this [excellent answer](https://codeforces.com/blog/entry/71562?#comment-559266) by [Um_nik](/profile/Um_nik "Легендарный гроссмейстер Um_nik"). All credit goes to him for the excellent proof. 36 37 [1255C - League of Leesins](/contest/1255/problem/C "Codeforces Round 601 (Div. 2)") 38 39 Author: [MikeMirzayanov](/profile/MikeMirzayanov "Штаб, MikeMirzayanov"). Prepared by [UncleGrandpa](/profile/UncleGrandpa "Мастер UncleGrandpa") 40 41 **Tutorial** 42 43 Tutorial is loading... 44 45 [1254A - Кормление куриц](/contest/1254/problem/A "Codeforces Round 601 (Div. 1)") 46 47 Author: [I_love_tigersugar](/profile/I_love_tigersugar "Гроссмейстер I_love_tigersugar"). Prepared by [I_love_tigersugar](/profile/I_love_tigersugar "Гроссмейстер I_love_tigersugar") 48 49 **Tutorial** 50 51 Tutorial is loading... 52 53 **Source code** 54 55 ``` 56 #include<bits/stdc++.h> 57 #define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; i++) 58 #define FORD(i, b, a) for (int i = (b), _a = (a); i >= _a; i--) 59 #define REP(i, n) for (int i = 0, _n = (n); i < _n; i++) 60 #define FORE(i, v) for (__typeof((v).begin()) i = (v).begin(); i != (v).end(); i++) 61 #define ALL(v) (v).begin(), (v).end() 62 #define IS_INF(x) (std::isinf(x)) 63 #define IS_NAN(x) (std::isnan(x)) 64 #define fi first 65 #define se second 66 #define MASK(i) (1LL << (i)) 67 #define BIT(x, i) (((x) >> (i)) & 1) 68 #define div ___div 69 #define next ___next 70 #define prev ___prev 71 #define left ___left 72 #define right ___right 73 #define __builtin_popcount __builtin_popcountll 74 using namespace std; 75 template<class X, class Y> 76 bool minimize(X &x, const Y &y) { 77 X eps = 1e-9; 78 if (x > y + eps) { 79 x = y; 80 return true; 81 } else return false; 82 } 83 template<class X, class Y> 84 bool maximize(X &x, const Y &y) { 85 X eps = 1e-9; 86 if (x + eps < y) { 87 x = y; 88 return true; 89 } else return false; 90 } 91 template<class T> 92 T Abs(const T &x) { 93 return (x < 0 ? -x : x); 94 } 95 96 /* Author: Van Hanh Pham */ 97 98 /** END OF TEMPLATE - ACTUAL SOLUTION COMES HERE **/ 99 100 const string SYMBOLS = "QWERTYUIOPASDFGHJKLZXCVBNMqwertyuiopasdfghjklzxcvbnm1234567890"; 101 102 #define MAX 111 103 char board[MAX][MAX], res[MAX][MAX]; 104 int numRow, numCol, numChicken; 105 106 void process(void) { 107 memset(board, 0, sizeof board); 108 memset(res, 0, sizeof res); 109 110 scanf("%d%d%d", &numRow, &numCol, &numChicken); 111 FOR(i, 1, numRow) scanf("%s", board[i] + 1); 112 113 bool leftToRight = true; 114 vector<pair<int, int>> cells; 115 FOR(i, 1, numRow) { 116 if (leftToRight) { 117 FOR(j, 1, numCol) cells.push_back(make_pair(i, j)); 118 } else { 119 FORD(j, numCol, 1) cells.push_back(make_pair(i, j)); 120 } 121 leftToRight ^= 1; 122 } 123 124 int totRice = 0; 125 FOR(i, 1, numRow) FOR(j, 1, numCol) if (board[i][j] == 'R') totRice++; 126 int avg = totRice / numChicken; 127 int diff = totRice % numChicken == 0 ? 0 : 1; 128 129 REP(i, numChicken) { 130 int cntRice = 0; 131 while (true) { 132 int x = cells.back().fi, y = cells.back().se; 133 cells.pop_back(); 134 res[x][y] = SYMBOLS[i]; 135 if (board[x][y] == 'R') { 136 totRice--; 137 cntRice++; 138 } 139 if (cntRice < avg) continue; 140 if (avg * (numChicken - i - 1) <= totRice && totRice <= (avg + diff) * (numChicken - i - 1)) break; 141 } 142 } 143 while (!cells.empty()) { 144 int x = cells.back().fi, y = cells.back().se; 145 cells.pop_back(); 146 res[x][y] = SYMBOLS[numChicken - 1]; 147 } 148 149 FOR(i, 1, numRow) { 150 FOR(j, 1, numCol) printf("%c", res[i][j]); printf("\n"); 151 } 152 } 153 154 int main(void) { 155 int t; scanf("%d", &t); 156 REP(love, t) process(); 157 return 0; 158 } 159 160 /*** LOOK AT MY CODE. MY CODE IS AMAZING :D ***/ 161 ``` 162 163 [1254B1 - Отправьте коробки Алисе (упрощенная версия)](/contest/1254/problem/B1 "Codeforces Round 601 (Div. 1)") 164 165 Author: [MofK](/profile/MofK "Международный гроссмейстер MofK"). Prepared by [UncleGrandpa](/profile/UncleGrandpa "Мастер UncleGrandpa") 166 167 **Tutorial** 168 169 The problem asked you to move chocolate pieces between adjacent boxes so that the number of chocolate pieces in all boxes is divisible by $k$ ($k \gt 1$). 170 171 #### How to solve the problem for a specific $k$ 172 173 Now, it's clear that we will divide the array into segments, such that the sum of each segment is divisible by $k$, and move all chocolate pieces in that segment to a common box. Here we take notice of 2 things: 174 175 * First, in each segment, let $A$ be the array of all position with 1, then the position that we move all the 1 to is the median of that array $A$ (easy to prove). 176 * Second, the sum of each segment should be all equal to $k$. It's easy to see that if there exists some segment of sum $x*k$, then separating them into $x$ segments of sum $k$ will improve the result. 177 178 With that two observations, we can iterate from 1 to n, push each position with value 1 into a temp array, and whenever the size of array become k, we add to our result the sum of $|a_i-median|$ and clear the array. 179 180 #### Knowing how to solve for a specific $k$, how to solve the problem? 181 182 It is clear that $k$ must be a divisor of the total number of chocolate pieces. So we iterate through all possible $k$ and minimize our answer with the number of steps to make all numbers divisible by k. A number $\le 10^5$ has at most 128 divisors, and each calculation take $O(n)$ so the solution should pass easily. 183 184 **Source code** 185 186 ``` 187 #include <bits/stdc++.h> 188 189 using namespace std; 190 191 const int maxn = 1000006; 192 int n; 193 int a[maxn]; 194 vector <int> v; 195 196 long long cost(int p) { 197 long long ret = 0; 198 for (int i = 0; i < v.size(); i += p) { 199 int median = v[(i + i + p - 1) / 2]; 200 for (int j = i; j < i + p; ++j) 201 ret += abs(v[j] - median); 202 } 203 return ret; 204 } 205 206 int main(void) { 207 ios_base::sync_with_stdio(0); 208 cin.tie(NULL); 209 cin >> n; 210 for (int i = 1; i <= n; ++i) { 211 cin >> a[i]; 212 if (a[i] == 1) v.push_back(i); 213 } 214 if (v.size() == 1) { 215 cout << -1 << endl; 216 return 0; 217 } 218 long long ans = 1e18; 219 int tmp = v.size(), p = 2; 220 while (p * p <= tmp) { 221 if (tmp % p == 0) { 222 ans = min(ans, cost(p)); 223 while (tmp % p == 0) 224 tmp /= p; 225 } 226 ++p; 227 } 228 if (tmp > 1) 229 ans = min(ans, cost(tmp)); 230 cout << ans << endl; 231 return 0; 232 } 233 ``` 234 235 [1254B2 - Отправьте коробки Алисе (усложнённая версия)](/contest/1254/problem/B2 "Codeforces Round 601 (Div. 1)") 236 237 Author: [MofK](/profile/MofK "Международный гроссмейстер MofK"). Prepared by [MofK](/profile/MofK "Международный гроссмейстер MofK") and [UncleGrandpa](/profile/UncleGrandpa "Мастер UncleGrandpa") 238 239 **Tutorial** 240 241 The problem E2 is different from the problem E1 in some ways. Now all $A_i$ is at most $10^6$, and so is the number $n$. That makes our solution on E1 simply not usable in this problem. 242 243 #### A cute observation: 244 245 Let $S_i$ be the sum of $a_1 + a_2 + ... + a_i$. Now we see that: 246 247 * if we move a chocolate piece from box $i$ to box $i+1$, it is equivalent to decrease $S_i$ by 1. 248 * if we move a chocolate piece from box $i+1$ to box $i$, it is equivalent to increase $S_i$ by 1. 249 250 Wow, now each moving steps only affect one number. Next, we can see that if every $a_i$ is divisible by k, then so is every $S_i$. Thus, our problem is now transformed to: Given an array $S$. At each turn, you can choose one $S_i$ and increase (or decrease) it by one (except for $S_n$). Find the minimum number of steps to make all $S_i$ divisible by $k$. 251 252 #### How to solve the problem for a specific $k$ 253 254 An intuitive approach is to try to increase (or decrease) each $S_i$ to the nearest multiple of $k$. If such a configuration can be achieved then it will obviously be the best answer. The only concern is that: is there any scenario when there exists some $i$ such that $S_i \gt S_{i+1}$, which is indeed a violation? Fortunately, the answer is no. We can enforce the solution to iterate each $S_i$ from $1$ to $n-1$ and always choose to decrease if there is a tie. This way, the sequence $S$ will remain non-decreasing throughout the process. 255 256 So, the solution is as follows. Just iterate from $1$ to $n-1$ and for each $i$, add to our result $min(S_i\%k,k-S_i\%k)$. 257 258 #### Knowing how to solve for a specific $k$, how to solve the problem? 259 260 Again, like E1, it is clear that $k$ must be a divisor of the total number of chocolate pieces. But now the total number of chocolate pieces is at most $10^{12}$, which an iteration through all divisors will not be fast enough to fit in 1 second. (In fact, we did make just one single test case to block this solution. Nevertheless, on random testcases it runs super fast). 261 262 But if you have solved the problem to this phase already, you can easily realize that we only need to consider prime $k$, because if $k$ is composite then picking any prime divisors of it will lead to either a better result or an equal result. 263 264 That's it, there will be at most 12 distinct prime divisors. Each calculation takes $O(n)$. So the solution will also pass easily. 265 266 **Source code** 267 268 ``` 269 #include <bits/stdc++.h> 270 271 using namespace std; 272 273 const int maxn = 1000006; 274 int n; 275 long long a[maxn]; 276 long long s[maxn]; 277 278 long long cost(long long mod) { 279 long long ret = 0; 280 for (int i = 1; i <= n; ++i) 281 ret += min(s[i] % mod, mod - s[i] % mod); 282 return ret; 283 } 284 285 int main(void) { 286 ios_base::sync_with_stdio(0); 287 cin.tie(NULL); 288 cin >> n; 289 for (int i = 1; i <= n; ++i) { 290 cin >> a[i]; 291 s[i] = s[i-1] + a[i]; 292 } 293 if (s[n] == 1) { 294 cout << -1 << endl; 295 return 0; 296 } 297 long long ans = 1e18; 298 long long tmp = s[n], p = 2; 299 while (p * p <= tmp) { 300 if (tmp % p == 0) { 301 ans = min(ans, cost(p)); 302 while (tmp % p == 0) 303 tmp /= p; 304 } 305 ++p; 306 } 307 if (tmp > 1) 308 ans = min(ans, cost(tmp)); 309 cout << ans << endl; 310 return 0; 311 } 312 ``` 313 314 [1254C - Упорядочьте точки](/contest/1254/problem/C "Codeforces Round 601 (Div. 1)") 315 316 Author: [ngkan](/profile/ngkan "Мастер ngkan"). Prepared by [ngkan](/profile/ngkan "Мастер ngkan") 317 318 **Tutorial** 319 320 Tutorial is loading... 321 322 **Source code** 323 324 ``` 325 #include <bits/stdc++.h> 326 using namespace std; 327 328 int n; 329 330 void check_if_zero(long long x){ 331 if (x == 0) exit(0); 332 } 333 334 long long get_area(int a,int b,int c){ 335 long long result; 336 cout << 1 << ' ' << a << ' ' << b << ' ' << c << endl; 337 cin >> result; 338 check_if_zero(result); 339 assert(result > 0); 340 return result; 341 } 342 343 int get_sign(int o,int a,int b){ 344 int result; 345 cout << 2 << ' ' << o << ' ' << a << ' ' << b << endl; 346 cin >> result; 347 check_if_zero(result); 348 assert(abs(result) == 1); 349 return result; 350 } 351 352 vector <int> lef, rig; 353 354 void divide(){ 355 for(int i=3;i<=n;i++){ 356 int sign = get_sign(1, 2, i); 357 358 if (sign == 1) 359 lef.push_back(i); 360 else 361 rig.push_back(i); 362 } 363 } 364 365 long long area12[1005]; 366 367 void _do(vector<int> &lst){ 368 if (lst.size() <= 1) 369 return; 370 371 long long best = 0; 372 for(auto v: lst){ 373 area12[v] = get_area(1, 2, v); 374 if (area12[v] > area12[best]) 375 best = v; 376 } 377 378 vector <int> l, r; 379 for(auto v: lst){ 380 if (v == best) 381 continue; 382 383 if (get_sign(1, best, v) == 1) 384 l.push_back(v); 385 else 386 r.push_back(v); 387 } 388 389 sort(l.begin(), l.end(), [&](int x,int y){ 390 return area12[x] > area12[y]; 391 }); 392 sort(r.begin(), r.end(), [&](int x,int y){ 393 return area12[x] < area12[y]; 394 }); 395 396 lst.clear(); 397 for(auto v: r) lst.push_back(v); 398 lst.push_back(best); 399 for(auto v: l) lst.push_back(v); 400 } 401 402 void answer(){ 403 cout << 0 << ' ' << 1 << ' '; 404 for(auto v: rig) cout << v << ' '; 405 cout << 2 << ' '; 406 for(auto v: lef) cout << v << ' '; 407 cout << endl; 408 } 409 410 int main(){ 411 cin >> n; 412 assert(n >= 3); 413 414 divide(); // n-2 queries 415 _do(lef); 416 _do(rig); // 2*(n-2) - 1 or 2*(n-2) - 2 queries 417 answer(); 418 } 419 ``` 420 421 [1254D - Запросы на дереве](/contest/1254/problem/D "Codeforces Round 601 (Div. 1)") 422 423 Author: [I_love_tigersugar](/profile/I_love_tigersugar "Гроссмейстер I_love_tigersugar") Prepared by [I_love_tigersugar](/profile/I_love_tigersugar "Гроссмейстер I_love_tigersugar") 424 425 **Tutorial** 426 427 Tutorial is loading... 428 429 **Source code** 430 431 ``` 432 #include <bits/stdc++.h> 433 434 using namespace std; 435 436 const int maxn = 150005; 437 const int mod = 998244353; 438 const int heavy = 300; 439 int n, m, q; 440 vector <int> adj[maxn]; 441 int dad[maxn]; 442 int sz[maxn]; 443 vector <int> pos[maxn]; 444 int tour[2*maxn]; 445 vector <int> heavy_vector; 446 int weight[2*maxn]; 447 448 int pw(int x, int y) { 449 int r = 1; 450 while (y) { 451 if (y & 1) r = 1LL * r * x % mod; 452 x = 1LL * x * x % mod; 453 y >>= 1; 454 } 455 return r; 456 } 457 458 void dfs(int u) { 459 tour[++m] = u; 460 pos[u].push_back(m); 461 sz[u] = 1; 462 for (auto v: adj[u]) { 463 if (v == dad[u]) continue; 464 dad[v] = u; 465 dfs(v); 466 sz[u] += sz[v]; 467 tour[++m] = u; 468 pos[u].push_back(m); 469 } 470 } 471 472 int fwt[2*maxn]; 473 void upd(int l, int r, int d) { 474 for (int p = l; p <= m; p += p & -p) fwt[p] = (fwt[p] + d) % mod; 475 ++r; 476 for (int p = r; p <= m; p += p & -p) fwt[p] = (fwt[p] + mod - d) % mod; 477 } 478 int get(int p) { 479 int ret = 0; 480 for (; p; p -= p & -p) ret = (ret + fwt[p]) % mod; 481 return ret; 482 } 483 484 int main(void) { 485 ios_base::sync_with_stdio(0); 486 cin.tie(NULL); 487 cin >> n >> q; 488 int inv_n = pw(n, mod - 2); 489 for (int i = 1; i < n; ++i) { 490 int u, v; 491 cin >> u >> v; 492 adj[u].push_back(v); 493 adj[v].push_back(u); 494 } 495 496 dfs(1); 497 for (int i = 1; i <= n; ++i) if (adj[i].size() >= heavy) 498 heavy_vector.push_back(i); 499 500 while (q--) { 501 int type, v; 502 cin >> type >> v; 503 if (type == 1) { 504 int d; 505 cin >> d; 506 weight[v] = (weight[v] + d) % mod; 507 if (adj[v].size() < heavy) { 508 for (auto u: adj[v]) if (u != dad[v]) 509 upd(pos[u][0], pos[u].back(), 1LL * d * (n - sz[u]) % mod * inv_n % mod); 510 if (v == 1) continue; 511 upd(1, pos[v][0] - 1, 1LL * d * sz[v] % mod * inv_n % mod); 512 upd(pos[v].back() + 1, m, 1LL * d * sz[v] % mod * inv_n % mod); 513 } 514 } 515 else { 516 int ans = (weight[v] + get(pos[v][0])) % mod; 517 for (auto u: heavy_vector) { 518 if (u == v) continue; 519 auto it = lower_bound(pos[u].begin(), pos[u].end(), pos[v][0]); 520 if (it == pos[u].begin() || it == pos[u].end()) 521 ans = (ans + 1LL * weight[u] * sz[u] % mod * inv_n) % mod; 522 else { 523 int p = tour[*(--it) + 1]; 524 ans = (ans + 1LL * weight[u] * (n - sz[p]) % mod * inv_n) % mod; 525 } 526 } 527 cout << ans << '\n'; 528 } 529 } 530 return 0; 531 } 532 ``` 533 534 [1254E - Отправьте дерево Чарли](/contest/1254/problem/E "Codeforces Round 601 (Div. 1)") 535 536 Author: [MofK](/profile/MofK "Международный гроссмейстер MofK") Prepared by: [MofK](/profile/MofK "Международный гроссмейстер MofK") 537 538 **Tutorial** 539 540 Tutorial is loading... 541 542 **Source code** 543 544 ``` 545 #include <bits/stdc++.h> 546 547 using namespace std; 548 549 const int mod = 1e9 + 7; 550 const int maxn = 500005; 551 552 int n; 553 vector <int> adj[maxn]; 554 int a[maxn]; 555 int dad[maxn]; 556 int h[maxn]; 557 vector <pair <int, int> > conditions[maxn]; 558 int nxt[maxn], prv[maxn], seen[maxn]; 559 560 void no(int ncase) { 561 cerr << ncase << endl; 562 cout << 0 << endl; 563 exit(0); 564 } 565 566 void dfs(int u) { 567 for (auto v: adj[u]) if (v != dad[u]) { 568 dad[v] = u; 569 h[v] = h[u] + 1; 570 dfs(v); 571 } 572 } 573 574 int cnt; ///total distance, must not be more than 2n-2 575 576 void go(int u, int v) { 577 if (u == v) no(0); 578 vector <int> from_u, to_v; 579 ///naive LCA works here as long as we exit upon finding a conflict 580 from_u.push_back(n + 1); ///first edge (fake) 581 to_v.push_back(n + 2); ///last edge (fake) 582 while (h[u] > h[v]) { 583 from_u.push_back(u); 584 u = dad[u]; 585 } 586 while (h[v] > h[u]) { 587 to_v.push_back(v); 588 v = dad[v]; 589 } 590 while (u != v) { 591 from_u.push_back(u); 592 u = dad[u]; 593 to_v.push_back(v); 594 v = dad[v]; 595 } 596 from_u.push_back(u); 597 from_u.insert(from_u.end(), to_v.rbegin(), to_v.rend()); 598 for (int i = 1; i + 1 < from_u.size(); ++i) 599 conditions[from_u[i]].push_back({from_u[i-1], from_u[i+1]}); 600 cnt += from_u.size() - 3; 601 if (cnt > 2 * n - 2) no(0); ///important break 602 } 603 604 int main(void) { 605 ios_base::sync_with_stdio(0); 606 cin.tie(NULL); 607 cin >> n; 608 for (int i = 1; i < n; ++i) { 609 int u, v; 610 cin >> u >> v; 611 adj[u].push_back(v); 612 adj[v].push_back(u); 613 } 614 for (int i = 1; i <= n; ++i) { 615 adj[i].push_back(n + 1); ///first edge (fake) 616 adj[i].push_back(n + 2); ///last edge (fake) 617 } 618 for (int i = 1; i <= n; ++i) cin >> a[i]; 619 620 if (n == 1) { 621 cout << 1 << endl; 622 exit(0); 623 } 624 625 dfs(1); 626 for (int i = 1; i <= n; ++i) if (a[i] != 0) go(i, a[i]); 627 628 ///answer 0 if: 629 ///1. there are 2 or more incoming/outgoing 630 ///conditions to/from an edge, or 631 ///2. there is a cycle, or 632 ///3. first (n+1) is connected to last (n+2), 633 ///but does not contain all other edges. 634 int ans = 1; 635 for (int i = 1; i <= n; ++i) { 636 ///check case 1 637 for (auto edge: conditions[i]) { 638 int u = edge.first, v = edge.second; 639 if (nxt[u] && nxt[u] != v) no(1); 640 if (prv[v] && prv[v] != u) no(1); 641 nxt[u] = v; 642 prv[v] = u; 643 } 644 ///check case 2 645 for (auto u: adj[i]) if (!seen[u]) { 646 seen[u] = 1; 647 int cur = nxt[u]; 648 while (cur) { 649 if (cur == u) no(2); 650 if (seen[cur]) break; 651 seen[cur] = 1; 652 cur = nxt[cur]; 653 } 654 } 655 ///check case 3 656 if (nxt[n+1]) { 657 int cur = n + 1, all = 1; 658 while (cur) { 659 if (cur == n + 2) break; 660 ++all; 661 cur = nxt[cur]; 662 } 663 if (cur == n + 2 && all < adj[i].size()) no(3); 664 } 665 ///all good - for now 666 int free = 0; 667 for (auto u: adj[i]) if (u <= n && !prv[u]) ///fake edges doesn't count 668 ++free; 669 if (prv[n+2]) --free; ///connected to last edge => not free 670 for (int j = 1; j <= free; ++j) ans = 1ll * ans * j % mod; 671 ///reset 672 for (auto u: adj[i]) nxt[u] = prv[u] = seen[u] = 0; 673 } 674 675 ///no conflicts 676 cout << ans << endl; 677 return 0; 678 } 679 ```