1610.md (20928B)
1 Source: https://codeforces.com/blog/entry/97179 2 3 ### [1610A - Anti Light's Cell Guessing](/contest/1610/problem/A "Codeforces Global Round 17") 4 5 Idea: [Anti-Light](/profile/Anti-Light "Expert Anti-Light"), Preparation: [DeadlyCritic](/profile/DeadlyCritic "Master DeadlyCritic") 6 7 **Hints** 8 9 **Hint 1** 10 11 $ans \le 2$ 12 13 **Hint 2** 14 15 If $n = 1$ and $m = 1$ then $ans = 0$. [](https://emoji.gg/emoji/5500-thosewhoknow) 16 17 **Solution** 18 19 Tutorial is loading... 20 21 **Implementation** 22 23 ``` 24 #include <bits/stdc++.h> 25 26 using namespace std; 27 28 int main() 29 { 30 ios::sync_with_stdio(false); 31 cin.tie(); 32 cout.tie(); 33 34 int t; 35 cin >> t; 36 while(t--){ 37 int n, m; 38 cin >> n >> m; 39 if(n == 1 && m == 1){ 40 cout << "0\n"; 41 } 42 else if(min(n, m) == 1){ 43 cout << "1\n"; 44 } 45 else cout << "2\n"; 46 } 47 } 48 ``` 49 50 ### [1610B - Kalindrome Array](/contest/1610/problem/B "Codeforces Global Round 17") 51 52 Idea: [Davoth](/profile/Davoth "Master Davoth"), [Keshi](/profile/Keshi "Grandmaster Keshi"), Preparation: [AmShZ](/profile/AmShZ "Grandmaster AmShZ"), [Keshi](/profile/Keshi "Grandmaster Keshi") 53 54 **Hint** 55 56 For an integer $x$ we can determine whether or not it's possible to make the array palindrome by removing some of the elements equal to $x$. 57 58 We claim that it is possible iff removing all appearances of $x$ makes the array palindrome. 59 60 Imagine we made the array palindrome by removing some of the elements equal to $x$. It's obvious that after removing the rest of the elements equal to $x$ the array remains palindrome. 61 62 **Solution** 63 64 $\textbf{Read the Hints and Assumptions before reading this.}$ 65 66 Tutorial is loading... 67 68 **Implementation** 69 70 ``` 71 //khodaya khodet komak kon 72 # include <bits/stdc++.h> 73 74 using namespace std; 75 76 typedef long long ll; 77 typedef long double ld; 78 typedef pair <int, int> pii; 79 typedef pair <pii, int> ppi; 80 typedef pair <int, pii> pip; 81 typedef pair <pii, pii> ppp; 82 typedef pair <ll, ll> pll; 83 84 # define A first 85 # define B second 86 # define endl '\n' 87 # define sep ' ' 88 # define all(x) x.begin(), x.end() 89 # define kill(x) return cout << x << endl, 0 90 # define SZ(x) int(x.size()) 91 # define lc id << 1 92 # define rc id << 1 | 1 93 # define fast_io ios::sync_with_stdio(0);cin.tie(0); cout.tie(0); 94 95 ll power(ll a, ll b, ll md) {return (!b ? 1 : (b & 1 ? a * power(a * a % md, b / 2, md) % md : power(a * a % md, b / 2, md) % md));} 96 97 const int xn = 2e5 + 10; 98 const int xm = - 20 + 10; 99 const int sq = 320; 100 const int inf = 1e9 + 10; 101 const ll INF = 1e18 + 10; 102 const ld eps = 1e-15; 103 const int mod = 998244353; 104 const int base = 257; 105 106 int qq, n, m, a[xn], b[xn]; 107 bool ans; 108 109 void check(int x){ 110 m = 0; 111 for (int i = 1; i <= n; ++ i) 112 if (a[i] != x) 113 b[++ m] = a[i]; 114 for (int i = 1; i <= m; ++ i) 115 if (b[i] != b[m + 1 - i]) 116 return; 117 ans = true; 118 } 119 120 int main(){ 121 fast_io; 122 123 cin >> qq; 124 while (qq --){ 125 cin >> n, ans = true; 126 for (int i = 1; i <= n; ++ i) 127 cin >> a[i]; 128 for (int i = 1; i <= n; ++ i){ 129 if (a[i] != a[n + 1 - i]){ 130 ans = false; 131 check(a[i]); 132 check(a[n + 1 - i]); 133 break; 134 } 135 } 136 if (ans) 137 cout << "YES" << endl; 138 else 139 cout << "NO" << endl; 140 } 141 142 return 0; 143 } 144 ``` 145 146 ### [1610C - Keshi Is Throwing a Party](/contest/1610/problem/C "Codeforces Global Round 17") 147 148 Idea: [Keshi](/profile/Keshi "Grandmaster Keshi"), Preparation: [Keshi](/profile/Keshi "Grandmaster Keshi") 149 150 **Hints** 151 152 **Hint 1** 153 154 Let $ans$ be the answer. For any $i \le ans$ it's possible to invite $\textbf{exactly}$ $i$ people, and for any $i \gt ans$ it's not possible to invite exactly $i$ people. 155 156 Because removing $1$ person from the party doesn't make anyone unhappy. So if we can invite $p_1, p_2, \ldots, p_k$, we also can invite $p_1, p_2, \ldots, p_{k - 1}$. 157 158 **Hint 2** 159 160 We use binary search to find the maximum $i$ that it's possible to invite exactly $i$ people. 161 162 Assume we want to invite $x$ people. If there are $i$ people poorer than person $v$, there are $x - 1 - i$ people richer than him. $i \le b_v$ and $x - 1 - i \le a_v$ so $x - 1 - a_v \le i \le b_v$. 163 164 **Solution** 165 166 $\textbf{Read the Hints and Assumptions before reading this.}$ 167 168 Tutorial is loading... 169 170 **Implementation** 171 172 ``` 173 //In the name of God 174 #include <bits/stdc++.h> 175 using namespace std; 176 177 typedef int ll; 178 typedef pair<ll, ll> pll; 179 180 const ll maxn = 2e5 + 100; 181 const ll mod = 1e9 + 7; 182 const ll inf = 1e9; 183 184 #define fast_io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); 185 #define file_io freopen("input.txt", "r+", stdin);freopen("output.txt", "w+", stdout); 186 #define pb push_back 187 #define Mp make_pair 188 #define F first 189 #define S second 190 #define Sz(x) ll((x).size()) 191 #define all(x) (x).begin(), (x).end() 192 193 ll q, n, a[maxn], b[maxn]; 194 195 bool ok(ll x){ 196 ll c = 0; 197 for(ll i = 0; i < n; i++){ 198 if(x - 1 - a[i] <= c && c <= b[i]) c++; 199 } 200 return c >= x; 201 } 202 203 int main(){ 204 fast_io; 205 206 cin >> q; 207 while(q--){ 208 cin >> n; 209 for(ll i = 0; i < n; i++){ 210 cin >> a[i] >> b[i]; 211 } 212 ll l = -1, r = n + 1, mid; 213 while(r - l > 1){ 214 mid = (l + r) >> 1; 215 if(ok(mid)) l = mid; 216 else r = mid; 217 } 218 cout << l << "\n"; 219 } 220 return 0; 221 } 222 ``` 223 224 ### [1610D - Not Quite Lee](/contest/1610/problem/D "Codeforces Global Round 17") 225 226 Idea: [DeadlyCritic](/profile/DeadlyCritic "Master DeadlyCritic"), Preparation: [DeadlyCritic](/profile/DeadlyCritic "Master DeadlyCritic") 227 228 **Hints** 229 230 **Hint 1** 231 232 First you should be able to check if an array $c$ of size $k$ is good or not. 233 234 **Hint 2** 235 236 If you choose some initial sequences $t_i$ for all $c_i$ that satisfy the first property, then you can reach any other set of sequences that satisfy the first property. Now you should check if a set of sequences exist that are reachable from your initial sequences and satisfy the second property or not. 237 238 **Hint 3** 239 240 If you do it correctly, and choose initial sequences such that $i$-th sequence starts from $0$ and ends with $c_i-1$ then you should end up with the following equaion : $\displaystyle x_1c_1 + x_2c_2+ \ldots + x_kc_k = -\sum{ \frac{c_i(c_i-1)}2}$. If this equation has an answer $(x_1, x_2, \ldots, x_k)$ then $c$ is good, otherwise it's not. 241 242 **Hint 4** 243 244 That equation has an answer if and only if $\displaystyle g = \gcd(c_1, c_2, \ldots, c_k)$ divides $\displaystyle \frac{c_i(c_i-1)}2$, this is not useful for the main problem in this state, try to go more in-depth. 245 246 **Hint 5** 247 248 I will frequently use the fact that if $y$ is odd and divides $x$, then $y$ divides $\frac x 2$, and if $y$ is even then $\frac y2$ divides $\frac x 2$. 249 250 **Solution** 251 252 Tutorial is loading... 253 254 **Implementation** 255 256 ``` 257 //In The Name of God 258 //I usually forget about the previous line... 259 260 #include <bits/stdc++.h> 261 262 #define IOS ios::sync_with_stdio(0), cin.tie(), cout.tie(); 263 264 using namespace std; 265 266 typedef long long ll; 267 268 const int maxBt = 30; 269 const int mod = 1e9+7; 270 271 int cnt[maxBt]; 272 273 int slv(){ 274 int n; 275 cin >> n; 276 277 int a[n]; 278 for(int i = 0; i < n; i++){ 279 cin >> a[i]; 280 } 281 282 int to[n+1]; //powers of 2 283 284 to[0] = 1; 285 for(int i = 1; i <= n; i++){ 286 to[i] = to[i-1]*2 % mod; 287 } 288 289 for(int i = 0; i < n; i++){ 290 int x = 0; 291 for(int k = 0; k < maxBt; k++){ 292 if(a[i] & 1)break; 293 a[i] >>= 1; 294 x++; 295 } 296 cnt[x]++; 297 } 298 299 int ans = to[n] - to[n-cnt[0]] + mod; 300 if(ans >= mod)ans -= mod; 301 302 int y = n-cnt[0]; 303 304 for(int l = 1; l < maxBt; l++){ 305 int x = y; 306 y -= cnt[l]; 307 if(x-y < 2)continue; 308 int delta = to[x-1]-to[y]+mod; 309 if(delta >= mod)delta -= mod; 310 ans += delta; 311 if(ans >= mod)ans -= mod; 312 } 313 314 return ans; 315 } 316 317 signed main(){ 318 IOS 319 320 cout << slv() << '\n'; 321 322 } 323 ``` 324 325 ### [1610E - AmShZ and G.O.A.T.](/contest/1610/problem/E "Codeforces Global Round 17") 326 327 Idea: [AmShZ](/profile/AmShZ "Grandmaster AmShZ"), Preparation: [AmShZ](/profile/AmShZ "Grandmaster AmShZ") 328 329 **Hints** 330 331 **Hint 1** 332 333 Firstly we prove that if array $c$ ($c_i \le c_{i + 1}$) of length $k$ is terrible, $c$ has a terrible subsequence of length $3$. 334 335 If there exists an index $i \ge 2$ that $c_{i + 1} - c_i \lt c_i - c_1$, sequence {$c_1, c_i, c_{i + 1}$} is terrible. Otherwise we can prove that $c_{\lceil \frac{k}{2} \rceil} \le AVG$ which is in contraction to the fact that $c$ is terrible. 336 337 **Hint 2** 338 339 We want to find the longest good subsequence of $a$. 340 341 Let $b_1, b_2, \ldots, b_k$ be values of a good subsequence. For every $i \ge 2$ we have $b_{i + 1} \ge 2 \cdot b_i - b_1$. 342 343 Let's fix the first element of the subsequence to be $a_s$. 344 345 **Solution** 346 347 $\textbf{Read the Hints and Assumptions before reading this.}$ 348 349 Tutorial is loading... 350 351 **Implementation** 352 353 ``` 354 //khodaya khodet komak kon 355 # include <bits/stdc++.h> 356 357 using namespace std; 358 359 const int xn = 2e5 + 10; 360 361 int qq, n, a[xn], ans, res, ptr; 362 363 int main(){ 364 ios::sync_with_stdio(0);cin.tie(0); cout.tie(0); 365 366 cin >> qq; 367 while (qq --){ 368 cin >> n, ans = 0; 369 for (int i = 1; i <= n; ++ i) 370 cin >> a[i]; 371 for (int i = 1; i <= n; ++ i){ 372 if (a[i] == a[i - 1]) 373 continue; 374 res = 0, ptr = i; 375 while (ptr <= n) 376 ptr = lower_bound(a + ptr + 1, a + n + 1, 2 * a[ptr] - a[i]) - a, ++ res; 377 ans = max(ans, res); 378 } 379 cout << n - ans << "\n"; 380 } 381 382 return 0; 383 } 384 ``` 385 386 ### [1610F - Mashtali: a Space Oddysey](/contest/1610/problem/F "Codeforces Global Round 17") 387 388 Idea: [AliShahali1382](/profile/AliShahali1382 "International Grandmaster AliShahali1382"), Preparation: [AliShahali1382](/profile/AliShahali1382 "International Grandmaster AliShahali1382") 389 390 **Hint** 391 392 Let's call $c_v$ as the sum of weights of all edges connected to vertex $v$. 393 394 It's obvious that when $c_v$ is even, $v$ would never be Oddysey. 395 396 Here we propose an algorithm to make all vertices with odd $c_v$ Oddysey. 397 398 **Solution** 399 400 $\textbf{Read the Hints and Assumptions before reading this.}$ 401 402 Tutorial is loading... 403 404 **Implementation** 405 406 ``` 407 #include <bits/stdc++.h> 408 #pragma GCC optimize ("O2,unroll-loops") 409 410 using namespace std; 411 typedef long long ll; 412 typedef long double ld; 413 typedef pair<int, int> pii; 414 typedef pair<ll, ll> pll; 415 #define all(x) x.begin(), x.end() 416 #define pb push_back 417 #define SZ(x) ((int)x.size()) 418 #define kill(x) return cout<<x<<'\n', 0; 419 420 const int inf=1000000010; 421 const ll INF=100000000000000100LL; 422 const int mod=1000000007; 423 const int MAXN=300010, LOG=19; 424 425 int n, m, mm, k, u, v, x, y, t, a, b; 426 int U[MAXN], V[MAXN], W[MAXN], ans[MAXN]; 427 int deg[MAXN], parr[MAXN][3], mark[MAXN]; 428 vector<int> G[MAXN][3], E[MAXN]; 429 vector<pii> G2[MAXN]; 430 431 inline void orient(int i, int u){ 432 if (u==U[i]){ 433 ans[i]=1; 434 deg[U[i]]-=W[i]; 435 deg[V[i]]+=W[i]; 436 } 437 else{ 438 ans[i]=2; 439 deg[U[i]]+=W[i]; 440 deg[V[i]]-=W[i]; 441 } 442 } 443 444 void MergePath(int i, int w){ 445 mm++; 446 int v=i; 447 while (1){ 448 while (SZ(G[v][w]) && mark[G[v][w].back()]) G[v][w].pop_back(); 449 if (G[v][w].empty()) break ; 450 int i=G[v][w].back(); 451 assert(!mark[i]); 452 mark[i]=1; 453 E[mm].pb(i); 454 int u=(U[i]^V[i]^v); 455 parr[u][w]^=1; 456 parr[v][w]^=1; 457 v=u; 458 } 459 if (E[mm].empty()){ 460 mm--; 461 return ; 462 } 463 G2[i].pb({v, mm}); 464 G2[v].pb({i, -mm}); 465 } 466 void dfs(int v){ 467 while (SZ(G2[v]) && mark[abs(G2[v].back().second)]) G2[v].pop_back(); 468 if (G2[v].empty()) return ; 469 int u=G2[v].back().first, id=G2[v].back().second; 470 if (id<0){ 471 id*=-1; 472 reverse(all(E[id])); 473 } 474 mark[id]=1; 475 for (int i:E[id]){ 476 orient(i, v); 477 v^=V[i]^U[i]; 478 } 479 assert(v==u); 480 dfs(u); 481 } 482 483 int main(){ 484 ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0); 485 cin>>n>>m; 486 for (int i=0; i<m; i++){ 487 cin>>U[i]>>V[i]>>W[i]; 488 parr[U[i]][W[i]]^=1; 489 parr[V[i]][W[i]]^=1; 490 G[U[i]][W[i]].pb(i); 491 G[V[i]][W[i]].pb(i); 492 } 493 int sum=0; 494 for (int i=1; i<=n; i++) sum+=parr[i][1]; 495 for (int i=1; i<=n; i++) for (int w:{1, 2}) if (parr[i][w]) MergePath(i, w); 496 for (int i=1; i<=n; i++) for (int w:{1, 2}) MergePath(i, w); 497 498 for (int i=0; i<m; i++){ 499 assert(mark[i]); 500 mark[i]=0; 501 } 502 for (int i=1; i<=n; i++) if (SZ(G2[i])&1) dfs(i); 503 for (int i=1; i<=n; i++) dfs(i); 504 505 cout<<sum<<"\n"; 506 for (int i=0; i<m; i++) cout<<ans[i]; cout<<"\n"; 507 508 return 0; 509 } 510 ``` 511 512 ### [1610G - AmShZ Wins a Bet](/contest/1610/problem/G "Codeforces Global Round 17") 513 514 Idea: [AmShZ](/profile/AmShZ "Grandmaster AmShZ"), [Keshi](/profile/Keshi "Grandmaster Keshi"), Preparation: [AmShZ](/profile/AmShZ "Grandmaster AmShZ"), [Keshi](/profile/Keshi "Grandmaster Keshi"), [alireza_kaviani](/profile/alireza_kaviani "International Grandmaster alireza_kaviani"), [AliShahali1382](/profile/AliShahali1382 "International Grandmaster AliShahali1382") 515 516 **Hints** 517 518 **Hint 1** 519 520 We can prove that there exists a way to achieve the lexicographically minimum by removing some balanced substrings. (A sequence of brackets is called balanced if one can turn it into a valid math expression by adding characters "+" and "1".) 521 522 We will remove some pairs of indices. If there is a pair that we don't remove all the characters between them, by using that character instead of one the initial ones the answer either stays the same or becomes lexicographically smaller. 523 524 Because if the character in between is "(", changing the pair is like moving a "(" closer to the front of the outcome which will make it smaller. And if it's ")", changing the pair is like moving a ")" farther from the front of the outcome which will make it smaller. 525 526 **Hint 2** 527 528 For each $i$ find the shortest non-empty balanced substring that starts in index $i$. Let the length of this substring be $l$. Set $nxt_i$ as $i + l$, or $i$ if no such substring exists. 529 530 For each $i$ we either keep the $i$-th character or remove every character in $[i, nxt_i)$ interval. 531 532 Imagine we somehow store the answer for each suffix. Then $ans_i = \min(s_i + ans_{i + 1}, ans_{nxt_i})$. 533 534 **Solution** 535 536 $\textbf{Read the Hints and Assumptions before reading this.}$ 537 538 Tutorial is loading... 539 540 **Implementation** 541 542 ``` 543 //In the name of God 544 #include <bits/stdc++.h> 545 using namespace std; 546 547 typedef long long ll; 548 typedef pair<ll, ll> pll; 549 550 const ll maxn = 3e5 + 100; 551 const ll lg = 20; 552 const ll mod = 1e9 + 7; 553 const ll inf = 1e18; 554 555 #define fast_io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); 556 #define file_io freopen("input.txt", "r+", stdin);freopen("output.txt", "w+", stdout); 557 #define pb push_back 558 #define Mp make_pair 559 #define F first 560 #define S second 561 #define Sz(x) ll((x).size()) 562 #define all(x) (x).begin(), (x).end() 563 564 ll n, par[maxn][lg], h[maxn][lg], ls[maxn + maxn], ps[maxn], nxt[maxn], a[maxn], d[maxn], p[maxn]; 565 string s; 566 567 ll check(ll v, ll u){ 568 for(ll i = lg; i--;){ 569 if(d[v] < (1 << i) || d[u] < (1 << i)) continue; 570 if(h[v][i] == h[u][i]){ 571 v = par[v][i]; 572 u = par[u][i]; 573 } 574 } 575 if(d[v] == 0) return 1; 576 return (h[v][0] < h[u][0]); 577 } 578 579 int main(){ 580 fast_io; 581 p[0] = 1; 582 for(ll i = 1; i < maxn; i++){ 583 p[i] = p[i - 1] * 2 % mod; 584 } 585 586 cin >> s; 587 n = Sz(s); 588 s = ' ' + s; 589 for(ll i = 1; i <= n; i++){ 590 ps[i] = ps[i - 1] + (s[i] == '(' ? 1 : -1); 591 } 592 for(ll i = n + 1; i > 0; i--){ 593 nxt[i] = i; 594 if(s[i] == '(' && ls[ps[i - 1] + maxn]){ 595 nxt[i] = ls[ps[i - 1] + maxn]; 596 } 597 ls[ps[i - 1] + maxn] = i; 598 } 599 a[n + 1] = n + 1; 600 for(ll i = n; i > 0; i--){ 601 par[i][0] = a[i + 1]; 602 h[i][0] = (s[i] == '(' ? 0 : 1); 603 d[i] = d[par[i][0]] + 1; 604 for(ll j = 1; j < lg; j++){ 605 if(d[i] < (1 << j)) break; 606 par[i][j] = par[par[i][j - 1]][j - 1]; 607 h[i][j] = (h[i][j - 1] * p[(1 << (j - 1))] + h[par[i][j - 1]][j - 1]) % mod; 608 } 609 a[i] = i; 610 if(check(a[nxt[i]], i)){ 611 a[i] = a[nxt[i]]; 612 } 613 } 614 ll v = a[1]; 615 while(v != n + 1){ 616 cout << (h[v][0] ? ')' : '('); 617 v = par[v][0]; 618 } 619 cout << "\n"; 620 621 return 0; 622 } 623 ``` 624 625 ### [1610H - Squid Game](/contest/1610/problem/H "Codeforces Global Round 17") 626 627 Idea: [Tet](/profile/Tet "Candidate Master Tet"), [AliShahali1382](/profile/AliShahali1382 "International Grandmaster AliShahali1382"), Preparation: [AliShahali1382](/profile/AliShahali1382 "International Grandmaster AliShahali1382") 628 629 **Solution** 630 631 Tutorial is loading... 632 633 **Implementation** 634 635 ``` 636 #include <bits/stdc++.h> 637 #pragma GCC optimize ("O2,unroll-loops") 638 639 using namespace std; 640 typedef long long ll; 641 typedef long double ld; 642 typedef pair<int, int> pii; 643 typedef pair<pii, int> piii; 644 typedef pair<ll, ll> pll; 645 #define debug(x) cerr<<#x<<'='<<(x)<<endl; 646 #define debugp(x) cerr<<#x<<"= {"<<(x.first)<<", "<<(x.second)<<"}"<<endl; 647 #define debug2(x, y) cerr<<"{"<<#x<<", "<<#y<<"} = {"<<(x)<<", "<<(y)<<"}"<<endl; 648 #define debugv(v) {cerr<<#v<<" : ";for (auto x:v) cerr<<x<<' ';cerr<<endl;} 649 #define all(x) x.begin(), x.end() 650 #define pb push_back 651 #define SZ(x) ((int)x.size()) 652 #define kill(x) return cout<<x<<'\n', 0; 653 654 const int inf=1000000010; 655 const ll INF=100000000000000100LL; 656 const int mod=1000000007; 657 const int MAXN=300010, LOG=19; 658 659 int n, m, k, u, v, x, y, t, a, b, ans; 660 int par[LOG][MAXN], h[MAXN], P[MAXN]; 661 int stt[MAXN], fnt[MAXN], timer=1; 662 int fen[MAXN]; 663 vector<int> G[MAXN], vec[MAXN], out; 664 665 int GetPar(int v, int k){ 666 for (int i=0; k; i++) if (k&(1<<i)){ 667 k^=(1<<i); 668 v=par[i][v]; 669 } 670 return v; 671 } 672 inline void add(int pos, int val){ 673 for (; pos<MAXN; pos+=pos&-pos) fen[pos]+=val; 674 } 675 inline int get(int pos){ 676 int res=0; 677 for (; pos; pos-=pos&-pos) res+=fen[pos]; 678 return res; 679 } 680 inline int get2(int v){ return get(fnt[v]-1)-get(stt[v]-1);} 681 void dfs(int node){ 682 stt[node]=timer++; 683 for (int v:G[node]) dfs(v); 684 fnt[node]=timer; 685 } 686 687 int main(){ 688 ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0); 689 cin>>n>>m; 690 for (int i=2; i<=n; i++){ 691 cin>>par[0][i]; 692 G[par[0][i]].pb(i); 693 h[i]=h[par[0][i]]+1; 694 for (int j=1; j<LOG; j++) 695 par[j][i]=par[j-1][par[j-1][i]]; 696 } 697 dfs(1); 698 while (m--){ 699 cin>>x>>y; 700 if (h[x]>h[y]) swap(x, y); 701 if (par[0][y]==x) kill(-1) 702 vec[x].pb(y); 703 } 704 iota(P+1, P+n+1, 1); 705 sort(P+1, P+n+1, [](int i, int j){ return h[i]>h[j];}); 706 vector<pii> crossE; 707 for (int i=1; i<=n; i++){ 708 int x=P[i]; 709 for (int y:vec[x]){ 710 if (h[x]==h[y]){ 711 crossE.pb({x, y}); 712 continue ; 713 } 714 int yy=GetPar(y, h[y]-h[x]-1); 715 if (par[0][yy]!=x){ 716 crossE.pb({x, y}); 717 continue ; 718 } 719 if (get2(yy)-get2(y)) continue ; 720 ans++; 721 out.pb(yy); 722 add(stt[yy], +1); 723 } 724 } 725 for (pii p:crossE){ 726 int x=p.first, y=p.second; 727 if (get2(x)+get2(y)<ans) continue ; 728 out.pb(1); 729 ans++; 730 break ; 731 } 732 cout<<ans<<"\n"; 733 734 return 0; 735 } 736 ``` 737 738 ### [1610I - Mashtali vs AtCoder](/contest/1610/problem/I "Codeforces Global Round 17") 739 740 Idea: [AliShahali1382](/profile/AliShahali1382 "International Grandmaster AliShahali1382"), Preparation: [AliShahali1382](/profile/AliShahali1382 "International Grandmaster AliShahali1382") 741 742 **Solution** 743 744 Tutorial is loading... 745 746 **Implementation** 747 748 ``` 749 #include <bits/stdc++.h> 750 #pragma GCC optimize ("O2,unroll-loops") 751 //#pragma GCC optimize("no-stack-protector,fast-math") 752 //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") 753 754 using namespace std; 755 typedef long long ll; 756 typedef long double ld; 757 typedef pair<int, int> pii; 758 typedef pair<pii, int> piii; 759 typedef pair<ll, ll> pll; 760 #define debug(x) cerr<<#x<<'='<<(x)<<endl; 761 #define debugp(x) cerr<<#x<<"= {"<<(x.first)<<", "<<(x.second)<<"}"<<endl; 762 #define debug2(x, y) cerr<<"{"<<#x<<", "<<#y<<"} = {"<<(x)<<", "<<(y)<<"}"<<endl; 763 #define debugv(v) {cerr<<#v<<" : ";for (auto x:v) cerr<<x<<' ';cerr<<endl;} 764 #define all(x) x.begin(), x.end() 765 #define pb push_back 766 #define SZ(x) ((int)x.size()) 767 #define kill(x) return cout<<x<<'\n', 0; 768 769 const int inf=1000000010; 770 const ll INF=100000000000000100LL; 771 const int mod=1000000007; 772 const int MAXN=300010, LOG=20; 773 774 int n, m, k, u, v, x, y, t, a, b, ans; 775 int par[MAXN], dp[MAXN], dead[MAXN]; 776 vector<int> G[MAXN]; 777 778 void dfs(int node){ 779 for (int v:G[node]) if (v!=par[node]){ 780 par[v]=node; 781 dfs(v); 782 dp[node]^=dp[v]+1; 783 } 784 } 785 786 int main(){ 787 ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0); 788 //freopen("input.txt", "r", stdin); 789 //freopen("output.txt", "w", stdout); 790 cin>>n; 791 for (int i=1; i<n; i++){ 792 cin>>u>>v; 793 G[u].pb(v); 794 G[v].pb(u); 795 } 796 dfs(1); 797 ans=dp[1]; 798 cout<<1+(ans==0); 799 dead[1]=1; 800 for (int i=2; i<=n; i++){ 801 vector<int> vec; 802 int v=i; 803 while (!dead[v]){ 804 vec.pb(v); 805 dead[v]=1; 806 v=par[v]; 807 } 808 reverse(all(vec)); 809 for (int v:vec){ 810 // Kill v 811 ans^=dp[v]+1; 812 ans^=dp[v]; 813 ans^=1; 814 } 815 cout<<1+(ans==0); 816 } 817 cout<<"\n"; 818 819 return 0; 820 } 821 ```