codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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$. [![ThoseWhoKnow](/predownloaded/2b/a7/2ba712923bc18592fd3953a9431a0a98097826d2.png)](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 ```