1336.md (16684B)
1 Source: https://codeforces.com/blog/entry/76099 2 3 [1337A - Ichihime and Triangle](/contest/1337/problem/A "Codeforces Round 635 (Div. 2)") 4 5 Idea: [Sulfox](/profile/Sulfox "International Master Sulfox") 6 7 **Tutorial** 8 9 Tutorial is loading... 10 11 **Solution by Sooke** 12 13 ``` 14 #include <bits/stdc++.h> 15 using namespace std; 16 17 int t, a, b, c, d; 18 19 int main() { 20 for (cin >> t; t; t--) { 21 cin >> a >> b >> c >> d; 22 cout << b << " " << c << " " << c << endl; 23 } 24 return 0; 25 } 26 ``` 27 28 [1337B - Kana and Dragon Quest game](/contest/1337/problem/B "Codeforces Round 635 (Div. 2)") 29 30 Idea: [EternalAlexander](/profile/EternalAlexander "Master EternalAlexander") 31 32 **Tutorial** 33 34 Tutorial is loading... 35 36 **Solution by EternalAlexander** 37 38 ``` 39 #include <bits/stdc++.h> 40 int x,n,m,t; 41 void solve(){ 42 scanf("%d%d%d",&x,&n,&m); 43 while (x>0&&n&&x/2+10<x){n--;x=x/2+10;} 44 if (x<=m*10)printf("YES\n"); 45 else printf("NO\n"); 46 } 47 int main(){ 48 scanf("%d",&t); 49 while(t--)solve(); 50 return 0; 51 } 52 ``` 53 54 [1336A - Linova and Kingdom](/contest/1336/problem/A "Codeforces Round 635 (Div. 1)") 55 56 Idea: [EternalAlexander](/profile/EternalAlexander "Master EternalAlexander") 57 58 **Tutorial** 59 60 Tutorial is loading... 61 62 **Solution by EternalAlexander** 63 64 ``` 65 #include <bits/stdc++.h> 66 #define maxn 200005 67 std::vector<int>conj[maxn]; 68 int n,k,u,v,depth[maxn]={0},size[maxn]={0},det[maxn]; 69 long long ans=0; 70 int cmp(int a,int b){return a>b;} 71 int dfs(int u,int f){depth[u]=depth[f]+1;size[u]=1; 72 for (int i=0;i<conj[u].size();++i){ 73 if ((v=conj[u][i])==f)continue; 74 size[u]+=dfs(v,u); 75 }det[u]=size[u]-depth[u];return size[u]; 76 } 77 int main(){ 78 scanf("%d%d",&n,&k); 79 for (int i=1;i<n;++i){ 80 scanf("%d%d",&u,&v);conj[u].push_back(v);conj[v].push_back(u); 81 }dfs(1,0); 82 std::nth_element(det+1,det+n-k,det+n+1,cmp); 83 for (int i=1;i<=n-k;++i)ans+=det[i];std::cout<<ans; 84 return 0; 85 } 86 ``` 87 88 [1336B - Xenia and Colorful Gems](/contest/1336/problem/B "Codeforces Round 635 (Div. 1)") 89 90 Idea: [ustze](/profile/ustze "Master ustze") & [isaf27](/profile/isaf27 "International Grandmaster isaf27") 91 92 **Tutorial** 93 94 Tutorial is loading... 95 96 **Solution by Sooke** 97 98 ``` 99 #include <bits/stdc++.h> 100 using namespace std; 101 102 int t, nr, ng, nb; 103 long long ans; 104 105 long long sq(int x) { return 1ll * x * x; } 106 107 void solve(vector<int> a, vector<int> b, vector<int> c) { 108 for (auto x : a) { 109 auto y = lower_bound(b.begin(), b.end(), x); 110 auto z = upper_bound(c.begin(), c.end(), x); 111 if (y == b.end() || z == c.begin()) { continue; } 112 z--; ans = min(ans, sq(x - *y) + sq(*y - *z) + sq(*z - x)); 113 } 114 } 115 116 int main() { 117 for (cin >> t; t; t--) { 118 cin >> nr >> ng >> nb; 119 vector<int> r(nr), g(ng), b(nb); 120 for (int i = 0; i < nr; i++) { cin >> r[i]; } 121 for (int i = 0; i < ng; i++) { cin >> g[i]; } 122 for (int i = 0; i < nb; i++) { cin >> b[i]; } 123 sort(r.begin(), r.end()); 124 sort(g.begin(), g.end()); 125 sort(b.begin(), b.end()); 126 ans = 9e18; 127 solve(r, g, b); solve(r, b, g); 128 solve(g, b, r); solve(g, r, b); 129 solve(b, r, g); solve(b, g, r); 130 cout << ans << endl; 131 } 132 return 0; 133 } 134 ``` 135 136 [1336C - Kaavi and Magic Spell](/contest/1336/problem/C "Codeforces Round 635 (Div. 1)") 137 138 Idea: [EternalAlexander](/profile/EternalAlexander "Master EternalAlexander") 139 140 **Tutorial** 141 142 Tutorial is loading... 143 144 **Solution by ouuan** 145 146 ``` 147 #include <iostream> 148 #include <string> 149 #include <vector> 150 151 using namespace std; 152 153 const int mod = 998244353; 154 155 int main() 156 { 157 string s, t; 158 159 cin >> s >> t; 160 int n = s.size(); 161 int m = t.size(); 162 163 vector<vector<int> > f(n + 1, vector<int>(m + 1)); 164 165 f[n][0] = 1; 166 167 for (int i = n - 1; i >= 1; --i) 168 { 169 for (int j = 0; j <= m; ++j) 170 { 171 if (j == 0) 172 { 173 if (i >= m) f[i][0] = n - i + 1; 174 else if (s[i] == t[i]) f[i][0] = f[i + 1][0]; 175 } 176 else if (j == m) 177 { 178 f[i][m] = 2 * f[i + 1][m] % mod; 179 if (s[i] == t[m - 1]) f[i][m] = (f[i][m] + f[i + 1][m - 1]) % mod; 180 } 181 else 182 { 183 if (i + j >= m || s[i] == t[i + j]) f[i][j] = f[i + 1][j]; 184 if (s[i] == t[j - 1]) f[i][j] = (f[i][j] + f[i + 1][j - 1]) % mod; 185 } 186 } 187 } 188 189 int ans = f[1][m]; 190 for (int i = 0; i < m; ++i) if (t[i] == s[0]) ans = (ans + f[1][i]) % mod; 191 ans = ans * 2 % mod; 192 193 cout << ans; 194 195 return 0; 196 } 197 ``` 198 199 [1336D - Yui and Mahjong Set](/contest/1336/problem/D "Codeforces Round 635 (Div. 1)") 200 201 Idea: [Sulfox](/profile/Sulfox "International Master Sulfox") 202 203 **Tutorial** 204 205 Tutorial is loading... 206 207 [PinkRabbitAFO](/profile/PinkRabbitAFO "International Grandmaster PinkRabbitAFO") gives another solution which inserts tiles with value $1$, $2$, $\ldots$, $n-1$, $1$ in order. See more details [here](https://codeforces.com/blog/entry/76092). 208 209 **Solution by Sooke** 210 211 ``` 212 #include <bits/stdc++.h> 213 using namespace std; 214 215 int n, s1, s2, t1, t2, d1[105], d2[105], a[105]; 216 217 int main() { 218 cin >> n >> s1 >> s2; 219 for (int i = n - 1; i >= 0; i--) { 220 cout << "+ " << (i > 2 ? i : i % 2 + 1) << endl; 221 t1 = s1; t2 = s2; cin >> s1 >> s2; 222 d1[i] = s1 - t1; d2[i] = s2 - t2; 223 } 224 a[1] = sqrt(d1[0] * 2); 225 a[3] = d2[0] - d2[2] - 1; 226 a[2] = d2[2] / (a[3] + 1); 227 a[4] = d2[1] / (a[3] + 1) - a[1] - 2; 228 for (int i = 5; i <= n; i++) { 229 a[i] = (d2[i - 2] - a[i - 4] * a[i - 3]) / (a[i - 1] + 1) - a[i - 3] - 1; 230 } 231 cout << "!"; a[n]++; 232 for (int i = 1; i <= n; i++) { cout << " " << a[i]; } 233 cout << endl; 234 return 0; 235 } 236 ``` 237 238 **Solution by PinkRabbit** 239 240 ``` 241 #include <cstdio> 242 243 const int MN = 105; 244 245 int N, lstv1, lstv2, v1, v2; 246 int dv1[MN], dv2[MN], Tag[MN], Ans[MN]; 247 248 int main() { 249 scanf("%d", &N); 250 scanf("%d%d", &lstv1, &lstv2); 251 for (int i = 1; i < N; ++i) { 252 printf("+ %d\n", i), fflush(stdout); 253 scanf("%d%d", &v1, &v2); 254 dv1[i] = v1 - lstv1, dv2[i] = v2 - lstv2; 255 if (dv1[i] > 0) 256 for (int x = 2; x <= N; ++x) 257 if (x * (x - 1) / 2 == dv1[i]) { 258 Tag[i] = x; break; 259 } 260 lstv1 = v1, lstv2 = v2; 261 } 262 printf("+ 1\n"), fflush(stdout); 263 scanf("%d%d", &v1, &v2); 264 int ndv1 = v1 - lstv1, ndv2 = v2 - lstv2; 265 for (int x = 0; x <= N; ++x) 266 if (x * (x + 1) / 2 == ndv1) { 267 Ans[1] = x; break; 268 } 269 int delta = ndv2 - dv2[1] - 1; // delta = a[2] + a[3] 270 if (Tag[2] >= 2) Ans[2] = Tag[2], Ans[3] = delta - Ans[2]; 271 else if (Tag[3] >= 2) Ans[3] = Tag[3], Ans[2] = delta - Ans[3]; 272 else if (delta == 0) Ans[3] = Ans[2] = 0; 273 else if (delta == 2) Ans[3] = Ans[2] = 1; 274 else if (dv2[2] > 0) Ans[2] = 0, Ans[3] = 1; 275 else Ans[2] = 1, Ans[3] = 0; 276 for (int i = 3; i <= N - 2; ++i) { 277 if (Tag[i + 1] >= 2) { 278 Ans[i + 1] = Tag[i + 1]; 279 continue; 280 } 281 if ((Ans[i - 2] + 1) * (Ans[i - 1] + 1) == dv2[i]) Ans[i + 1] = 0; 282 else Ans[i + 1] = 1; 283 } 284 Ans[N] = (dv2[N - 1] - (Ans[N - 3] + 1) * (Ans[N - 2] + 1)) / (Ans[N - 2] + 1); 285 printf("!"); 286 for (int i = 1; i <= N; ++i) printf(" %d", Ans[i]); 287 puts(""), fflush(stdout); 288 return 0; 289 } 290 ``` 291 292 [1336E1 - Chiori and Doll Picking (easy version)](/contest/1336/problem/E1 "Codeforces Round 635 (Div. 1)") and [1336E2 - Chiori and Doll Picking (hard version)](/contest/1336/problem/E2 "Codeforces Round 635 (Div. 1)") 293 294 Idea: [Sulfox](/profile/Sulfox "International Master Sulfox") 295 296 **Tutorial** 297 298 Tutorial is loading... 299 300 **Solution by Sooke** 301 302 ``` 303 #include <bits/stdc++.h> 304 using namespace std; 305 306 const int mod = 998244353, inv2 = 499122177; 307 const int M = 64; 308 309 int n, m, k, p[M], c[M][M]; 310 long long a[M], b[M], f[M]; 311 312 void dfs(int i, long long x) { 313 if (i == k) { p[__builtin_popcountll(x)]++; return; } 314 dfs(i + 1, x); dfs(i + 1, x ^ a[i]); 315 } 316 317 int main() { 318 cin >> n >> m; 319 for (int i = 0; i < n; i++) { 320 long long x; cin >> x; 321 for (int j = m; j >= 0; j--) { 322 if (x >> j & 1) { 323 if (!f[j]) { f[j] = x; break; } 324 x ^= f[j]; 325 } 326 } 327 } 328 for (int i = 0; i < m; i++) { 329 if (f[i]) { 330 for (int j = 0; j < i; j++) { 331 if (f[i] >> j & 1) { f[i] ^= f[j]; } 332 } 333 for (int j = 0; j < m; j++) { 334 if (!f[j]) { a[k] = a[k] * 2 + (f[i] >> j & 1); } 335 } 336 a[k] |= 1ll << m - 1 - k; k++; 337 } 338 } 339 if (k <= 26) { 340 dfs(0, 0); 341 for (int i = 0; i <= m; i++) { 342 int ans = p[i]; 343 for (int j = 0; j < n - k; j++) { ans = ans * 2 % mod; } 344 cout << ans << " "; 345 } 346 } else { 347 k = m - k; swap(a, b); 348 for (int i = 0; i < k; i++) { 349 for (int j = 0; j < m - k; j++) { 350 if (b[j] >> i & 1) { a[i] |= 1ll << j; } 351 } 352 a[i] |= 1ll << m - 1 - i; 353 } 354 dfs(0, 0); 355 for (int i = 0; i <= m; i++) { 356 c[i][0] = 1; 357 for (int j = 1; j <= i; j++) { c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod; } 358 } 359 for (int i = 0; i <= m; i++) { 360 int ans = 0; 361 for (int j = 0; j <= m; j++) { 362 int coef = 0; 363 for (int k = 0; k <= i; k++) { 364 coef = (coef + (k & 1 ? -1ll : 1ll) * c[j][k] * c[m - j][i - k] % mod + mod) % mod; 365 } 366 ans = (ans + 1ll * coef * p[j]) % mod; 367 } 368 for (int j = 0; j < k; j++) { ans = 1ll * ans * inv2 % mod; } 369 for (int j = 0; j < n - m + k; j++) { ans = ans * 2 % mod; } 370 cout << ans << " "; 371 } 372 } 373 return 0; 374 } 375 ``` 376 377 **Bonus** 378 379 Solve the same problem with $m \le 63$. 380 381 [1336F - Journey](/contest/1336/problem/F "Codeforces Round 635 (Div. 1)") 382 383 Idea: [EternalAlexander](/profile/EternalAlexander "Master EternalAlexander") 384 385 **Tutorial** 386 387 First, let's choose an arbitrary root for the tree. Then for all pairs of paths, their LCA (lowest common ancestor) can be either different or the same. 388 389 Then, let's calculate the answer of pairs with different LCAs. In this case, if the intersection is not empty, it will be a vertical path as in the graph below. 390 391  392 393 Here path $G-H$ and path $E-F$ intersects at path $B-G$. 394 395 We can process all paths in decreasing order of the depth of their LCA. When processing a path $p$ we calculate the number of paths $q$, where $q$ is processed before $p$, and the edge-intersection of $p$ and $q$ is at least $k$. To do this we can plus one to the subtree of the nodes on the path $k$ edges away from the LCA (node $C$ and $D$ for path $G-H$ in the graph above), then we can query the value at the endpoints of the path (node $E$ and $F$ for path $E-F$). We can maintain this easily with BIT (binary indexed tree, or Fenwick tree). 396 397 Next, we calculate pairs with the same LCA. This case is harder. 398 399 For each node $u$ we calculate the number of pairs with the LCA $u$. 400 401  402 403 For a pair of path $(x_1,y_1)$ and $(x_2, y_2)$, there are still two cases we need to handle. 404 405 Let $dfn_x$ be the index of $x$ in the DFS order. For a path $(x,y)$ we assume that $dfn_x \lt dfn_y$ (otherwise you can just swap them) 406 407 In the first case ( the right one in the graph above, where $(x_1,y_1) = (B,E), (x_2,y_2) = (C,F)$ ), the intersection of $(x_1,y_1)$ and $(x_2,y_2)$ is the path that goes from $\operatorname{LCA}(x_1,x_2)$ to $\operatorname{LCA}(y_1,y_2)$ (path $A - D$) 408 409 In this case the intersection may cross over node $u$. 410 411 For all paths $(x,y)$ with the LCA $u$. We can build a virtual-tree over all $x$ of the paths, and on node $x$ we store the value of $y$. Let's do a dfs on the virtual-tree. On each node $a$ we calculate pairs $(x_1,y_1)$,$(x_2,y_2)$ that $\operatorname{LCA}(x_1,x_2) = a$. For $x_1$ , let's go from $a$ to $y_1$ for $k$ edges, assume the node we reached is $b$, all legal $y_2$ should be in the subtree of $b$. 412 413 We can use a segment tree on the DFS-order to maintain all $y$s in the subtree and merge them with the small-to-large trick, meanwhile, iterate over all $x_1$ in the smaller segment tree, count the valid $y_2$'s in the larger segment tree. 414 415 In fact, you can use HLD (heavy-light decomposition) instead of virtual-tree, which seems to be easier to implement. 416 417 Now note that the solution above is based on the fact that the intersection of $(x_1,y_1)$ and $(x_2,y_2)$ is the path that goes from $\operatorname{LCA}(x_1,x_2)$ to $\operatorname{LCA}(y_1,y_2)$. But it is not always true, so here we have another case to handle. 418 419 In this case, (the left one in the graph above), the intersection is definitely a vertical path that goes from $u$ to $\operatorname{LCA(y_1,x_2)}$. This can be solved similarly to the case of different LCAs. 420 421 The overall complexity of this solution is $O(m \log^2 m + n\log n)$. 422 423 **Solution by EternalAlexander** 424 425 ``` 426 #include <bits/stdc++.h> 427 #define maxn 200005 428 int n,m,k,u[maxn],v[maxn],ch[maxn<<6][2]={0},sum[maxn<<6]={0},pt[maxn],head[maxn]={0},tail=0,cnt=0,root[maxn]={0}, 429 anc[maxn][19]={0},son[maxn]={0},depth[maxn]={0},dfn[maxn],size[maxn],idx=0; 430 long long ans=0; 431 std::vector<int>in[maxn],vec[maxn]; 432 struct edge { 433 int v,next; 434 }edges[maxn<<1]; 435 void add_edge(int u,int v){ 436 edges[++tail].v=v; 437 edges[tail].next=head[u]; 438 head[u]=tail; 439 } 440 namespace BIT { 441 int sum[maxn<<2]={0}; 442 void add(int p,int x) {if (p==0) return;while (p<=n) {sum[p]+=x;p+=p&-p;}} 443 int query(int p) {int ans=0;while (p>0) {ans+=sum[p];p-=p&-p;}return ans;} 444 void Add(int l,int r){add(l,1);add(r+1,-1);} 445 } 446 void update(int x){sum[x]=sum[ch[x][0]]+sum[ch[x][1]];} 447 int insert(int rt,int l,int r,int p){ 448 if (!rt) rt=++cnt; 449 if (l==r) {sum[rt]++;return rt;} 450 int mid=(l+r)>>1; 451 if (p<=mid) ch[rt][0]=insert(ch[rt][0],l,mid,p); 452 else ch[rt][1]=insert(ch[rt][1],mid+1,r,p); 453 update(rt); 454 return rt; 455 } int merge(int u,int v){ 456 if (!u||!v)return u+v; 457 ch[u][0]=merge(ch[u][0],ch[v][0]); 458 ch[u][1]=merge(ch[u][1],ch[v][1]); 459 sum[u]=sum[u]+sum[v];return u; 460 } int query(int rt,int L,int R,int l,int r){ 461 if (l>R||r<L)return 0; 462 if (l<=L&&R<=r){return sum[rt];} 463 return query(ch[rt][0],L,(L+R)>>1,l,r)+query(ch[rt][1],((L+R)>>1)+1,R,l,r); 464 } 465 466 void dfs1(int u,int f){ 467 anc[u][0]=f;depth[u]=depth[f]+1;size[u]=1; 468 for (int i=1;i<=18;++i)anc[u][i]=anc[anc[u][i-1]][i-1]; 469 for (int i=head[u];i;i=edges[i].next){ 470 int v=edges[i].v; 471 if (v==f) continue; 472 dfs1(v,u);size[u]+=size[v]; 473 if (size[v]>size[son[u]])son[u]=v; 474 } 475 } void dfsn(int u){ 476 dfn[u]=++idx; 477 for (int i=head[u];i;i=edges[i].next){ 478 int v=edges[i].v; 479 if (v==son[u]||v==anc[u][0])continue; 480 dfsn(v); 481 }if (son[u]) dfsn(son[u]); 482 } 483 484 int lift(int u,int x){ 485 for (int i=18;i>=0;i--)if (x>=(1<<i)) {u=anc[u][i];x-=(1<<i);} 486 return u; 487 } 488 489 int lca(int u,int v){ 490 if (depth[u]<depth[v])std::swap(u,v); 491 for (int i=18;i>=0;i--)if (depth[anc[u][i]]>=depth[v])u=anc[u][i]; 492 if (u==v)return u; 493 for (int i=18;i>=0;i--)if (anc[u][i]!=anc[v][i]){u=anc[u][i];v=anc[v][i];} 494 return anc[u][0]; 495 } 496 497 void dfs3(int x,int rt){ 498 pt[x]=x;root[x]=0; 499 for (int i=0;i<in[x].size();++i) { 500 int d=in[x][i]; 501 int rd=std::max(0,k-(depth[u[d]]-depth[rt])); 502 if (depth[v[d]]-depth[rt]>=rd){ 503 int l=lift(v[d],depth[v[d]]-depth[rt]-rd); 504 ans+=query(root[x],1,n,dfn[l],dfn[l]+size[l]-1); 505 }root[x]=insert(root[x],1,n,dfn[v[d]]); 506 }for (int i=head[x];i;i=edges[i].next){ 507 int t=edges[i].v; 508 if (t==anc[x][0]||(rt==x&&t==son[x])) continue; 509 dfs3(t,rt); 510 if (in[pt[x]].size()<in[pt[t]].size()){ 511 std::swap(pt[x],pt[t]); 512 std::swap(root[x],root[t]); 513 }while (!in[pt[t]].empty()){ 514 int d=in[pt[t]][in[pt[t]].size()-1];in[pt[t]].pop_back(); 515 int rd=std::max(0,k-(depth[x]-depth[rt])); 516 if (depth[v[d]]-depth[rt]>=rd) { 517 int l=lift(v[d],(depth[v[d]]-depth[rt]-rd)); 518 ans+=query(root[x],1,n,dfn[l],dfn[l]+size[l]-1); 519 }in[pt[x]].push_back(d); 520 }root[x]=merge(root[x],root[t]); 521 } 522 } 523 524 void dfs2(int x){ 525 int len=vec[x].size(); 526 for (int i=head[x];i;i=edges[i].next)if (edges[i].v!=anc[x][0])dfs2(edges[i].v); 527 for (int i=0;i<len;++i)ans+=BIT::query(dfn[v[vec[x][i]]]); 528 for (int i=0;i<len;++i){ 529 int j=vec[x][i]; 530 if (depth[v[j]]-depth[x]>=k) { 531 int l=lift(v[j],depth[v[j]]-depth[x]-k); 532 BIT::Add(dfn[l],dfn[l]+size[l]-1); 533 } 534 }for (int i=0;i<len;++i){ans+=BIT::query(dfn[u[vec[x][i]]]);in[u[vec[x][i]]].push_back(vec[x][i]);} 535 dfs3(x,x); 536 while (!in[pt[x]].empty())in[pt[x]].pop_back(); 537 for (int i=0;i<len;++i){ 538 int j=vec[x][i]; 539 if (depth[u[j]]-depth[x]>=k) { 540 int l=lift(u[j],depth[u[j]]-depth[x]-k); 541 BIT::Add(dfn[l],dfn[l]+size[l]-1); 542 } 543 } 544 } 545 546 int main(){ 547 scanf("%d%d%d",&n,&m,&k); 548 for(int i=1;i<n;++i){ 549 int u,v; 550 scanf("%d%d",&u,&v); 551 add_edge(u,v); 552 add_edge(v,u); 553 }dfs1(1,0);dfsn(1); 554 for (int i=1;i<=m;++i){ 555 scanf("%d%d",&u[i],&v[i]); 556 if (dfn[u[i]]>dfn[v[i]]) std::swap(u[i],v[i]); 557 int l=lca(u[i],v[i]); 558 vec[l].push_back(i); 559 } dfs2(1); 560 std::cout<<ans; 561 return 0; 562 } 563 ```