1529.md (26644B)
1 Source: https://codeforces.com/blog/entry/91058 2 3 Hi, Codeforces! 4 5 [1529A - Eshag Loves Big Arrays](/contest/1529/problem/A "Codeforces Round 722 (Div. 2)") 6 7 problem idea and solution: [AmShZ](/profile/AmShZ "Grandmaster AmShZ") 8 9 **editorial** 10 11 Tutorial is loading... 12 13 **official solution** 14 15 ``` 16 // khodaya khodet komak kon 17 # include <bits/stdc++.h> 18 19 using namespace std; 20 21 typedef long long ll; 22 typedef long double ld; 23 typedef pair <int, int> pii; 24 typedef pair <pii, int> ppi; 25 typedef pair <int, pii> pip; 26 typedef pair <pii, pii> ppp; 27 typedef pair <ll, ll> pll; 28 29 # define A first 30 # define B second 31 # define endl '\n' 32 # define sep ' ' 33 # define all(x) x.begin(), x.end() 34 # define kill(x) return cout << x << endl, 0 35 # define SZ(x) int(x.size()) 36 # define lc id << 1 37 # define rc id << 1 | 1 38 39 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));} 40 41 const int xn = 1e2 + 10; 42 const int sq = 320; 43 const int inf = 1e9 + 10; 44 const ll INF = 1e18 + 10; 45 const int mod = 1e9 + 7;//998244353; 46 const int base = 257; 47 48 int qq, n, a[xn], mn, ans; 49 50 int main(){ 51 ios::sync_with_stdio(0);cin.tie(0); cout.tie(0); 52 cin >> qq; 53 while (qq --){ 54 cin >> n, mn = inf, ans = 0; 55 for (int i = 1; i <= n; ++ i) 56 cin >> a[i], mn = min(mn, a[i]); 57 for (int i = 1; i <= n; ++ i) 58 ans += a[i] != mn; 59 cout << ans << endl; 60 } 61 62 return 0; 63 } 64 ``` 65 66 [1529B - Sifid and Strange Subsequences](/contest/1529/problem/B "Codeforces Round 722 (Div. 2)") 67 68 problem idea and solution: [Davoth](/profile/Davoth "Candidate Master Davoth") 69 70 **editorial** 71 72 Tutorial is loading... 73 74 **official solution** 75 76 ``` 77 // khodaya khodet komak kon 78 // Nightcall - London Grammer 79 # include <bits/stdc++.h> 80 81 using namespace std; 82 83 typedef long long ll; 84 typedef long double ld; 85 typedef pair <int, int> pii; 86 typedef pair <pii, int> ppi; 87 typedef pair <int, pii> pip; 88 typedef pair <pii, pii> ppp; 89 typedef pair <ll, ll> pll; 90 91 # define A first 92 # define B second 93 # define endl '\n' 94 # define sep ' ' 95 # define all(x) x.begin(), x.end() 96 # define kill(x) return cout << x << endl, 0 97 # define SZ(x) int(x.size()) 98 # define lc id << 1 99 # define rc id << 1 | 1 100 101 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));} 102 103 const int xn = 1e5 + 10; 104 const int xm = - 20 + 10; 105 const int sq = 320; 106 const int inf = 1e9 + 10; 107 const ll INF = 1e18 + 10; 108 const int mod = 1e9 + 7;//998244353; 109 const int base = 257; 110 111 int qq, n, a[xn], ans, mn; 112 bool flag; 113 114 int main(){ 115 ios::sync_with_stdio(0);cin.tie(0); cout.tie(0); 116 117 cin >> qq; 118 while (qq --){ 119 cin >> n, ans = 0; 120 for (int i = 1; i <= n; ++ i) 121 cin >> a[i], ans += (a[i] <= 0); 122 sort(a + 1, a + n + 1), mn = inf; 123 for (int i = 1; i <= n; ++ i) 124 if (a[i] > 0) 125 mn = min(mn, a[i]); 126 flag = (mn < inf); 127 for (int i = 2; i <= n; ++ i) 128 if (a[i] <= 0) 129 flag &= (a[i] - a[i - 1] >= mn); 130 if (flag) 131 cout << ans + 1 << endl; 132 else 133 cout << ans << endl; 134 } 135 136 return 0; 137 } 138 ``` 139 140 [1528A - Parsa's Humongous Tree](/contest/1528/problem/A "Codeforces Round 722 (Div. 1)") 141 142 problem idea and solution: [shokouf](/profile/shokouf "Candidate Master shokouf"), [AmShZ](/profile/AmShZ "Grandmaster AmShZ") 143 144 **editorial** 145 146 Tutorial is loading... 147 148 **official solution** 149 150 ``` 151 // Call my Name and Save me from The Dark 152 #include <bits/stdc++.h> 153 154 using namespace std; 155 156 typedef long long int ll; 157 typedef pair<int, int> pii; 158 159 #define SZ(x) (int) x.size() 160 #define F first 161 #define S second 162 163 const int N = 2e5 + 10; 164 ll dp[2][N]; int A[2][N], n; vector<int> adj[N]; 165 166 void DFS(int v, int p = -1) { 167 dp[0][v] = dp[1][v] = 0; 168 for (int u : adj[v]) { 169 if (u == p) continue; 170 DFS(u, v); 171 dp[0][v] += max(abs(A[0][v] - A[1][u]) + dp[1][u], dp[0][u] + abs(A[0][v] - A[0][u])); 172 dp[1][v] += max(abs(A[1][v] - A[1][u]) + dp[1][u], dp[0][u] + abs(A[1][v] - A[0][u])); 173 } 174 } 175 176 void Solve() { 177 scanf("%d", &n); 178 for (int i = 1; i <= n; i++) scanf("%d%d", &A[0][i], &A[1][i]); 179 fill(adj + 1, adj + n + 1, vector<int>()); 180 for (int i = 1; i < n; i++) { 181 int u, v; scanf("%d%d", &u, &v); 182 adj[u].push_back(v); 183 adj[v].push_back(u); 184 } 185 DFS(1); 186 printf("%lld\n", max(dp[0][1], dp[1][1])); 187 } 188 189 int main() { 190 int t; scanf("%d", &t); 191 while (t--) Solve(); 192 return 0; 193 } 194 ``` 195 196 [1528B - Kavi on Pairing Duty](/contest/1528/problem/B "Codeforces Round 722 (Div. 1)") 197 198 problem idea and solution: [alireza_kaviani](/profile/alireza_kaviani "International Grandmaster alireza_kaviani") 199 200 **editorial** 201 202 Tutorial is loading... 203 204 **official solution** 205 206 ``` 207 #include <bits/stdc++.h> 208 using namespace std; 209 210 typedef long long ll; 211 typedef pair<ll, ll> pll; 212 typedef pair<int, int> pii; 213 214 #define X first 215 #define Y second 216 #define endl '\n' 217 218 const int N = 1e6 + 10; 219 const int MOD = 998244353; 220 221 int n, dp[N], S; 222 223 int main() { 224 ios_base::sync_with_stdio(false); cin.tie(nullptr); 225 cin >> n; 226 for (int i = 1; i <= n; i++) { 227 for (int j = i + i; j <= n; j += i) { 228 dp[j]++; 229 } 230 } 231 dp[0] = S = 1; 232 for (int i = 1; i <= n; i++) { 233 dp[i] = (dp[i] + S) % MOD; 234 S = (S + dp[i]) % MOD; 235 } 236 cout << dp[n] << endl; 237 return 0; 238 } 239 ``` 240 241 [1528C - Trees of Tranquillity](/contest/1528/problem/C "Codeforces Round 722 (Div. 1)") 242 243 problem idea and solution: [AliShahali1382](/profile/AliShahali1382 "International Grandmaster AliShahali1382") 244 245 **editorial** 246 247 Tutorial is loading... 248 249 **official solution** 250 251 ``` 252 #include <bits/stdc++.h> 253 #pragma GCC optimize ("O2,unroll-loops") 254 //#pragma GCC optimize("no-stack-protector,fast-math") 255 256 using namespace std; 257 typedef long long ll; 258 typedef long double ld; 259 typedef pair<int, int> pii; 260 typedef pair<pii, int> piii; 261 typedef pair<ll, ll> pll; 262 #define debug(x) cerr<<#x<<'='<<(x)<<endl; 263 #define debugp(x) cerr<<#x<<"= {"<<(x.first)<<", "<<(x.second)<<"}"<<endl; 264 #define debug2(x, y) cerr<<"{"<<#x<<", "<<#y<<"} = {"<<(x)<<", "<<(y)<<"}"<<endl; 265 #define debugv(v) {cerr<<#v<<" : ";for (auto x:v) cerr<<x<<' ';cerr<<endl;} 266 #define all(x) x.begin(), x.end() 267 #define pb push_back 268 #define kill(x) return cout<<x<<'\n', 0; 269 270 const int inf=1000000010; 271 const ll INF=1000000000000001000LL; 272 const int mod=1000000007; 273 const int MAXN=300010, LOG=20; 274 275 int n, m, k, u, v, x, y, t, a, b, ans; 276 int par1[MAXN], par2[MAXN]; 277 int stt[MAXN], fnt[MAXN], timer; 278 vector<int> G1[MAXN], G2[MAXN]; 279 set<pii> st; 280 281 int Add(int v){ 282 auto it=st.lower_bound({stt[v], v}); 283 if (it!=st.end() && fnt[it->second]<=fnt[v]) return -2; 284 if (it==st.begin()) return -1; 285 --it; 286 int res=it->second; 287 if (fnt[v]>fnt[res]) return -1; 288 st.erase(it); 289 return res; 290 } 291 void dfs1(int node){ 292 stt[node]=timer++; 293 for (int v:G2[node]) dfs1(v); 294 fnt[node]=timer; 295 } 296 void dfs2(int node){ 297 int res=Add(node); 298 if (res!=-2) st.insert({stt[node], node}); 299 ans=max(ans, (int)st.size()); 300 for (int v:G1[node]) dfs2(v); 301 if (res!=-2){ 302 st.erase({stt[node], node}); 303 if (res!=-1) st.insert({stt[res], res}); 304 } 305 } 306 307 void Solve(){ 308 cin>>n; 309 for (int i=1; i<=n; i++) G1[i].clear(), G2[i].clear(); 310 for (int i=2; i<=n; i++) cin>>par1[i], G1[par1[i]].pb(i); 311 for (int i=2; i<=n; i++) cin>>par2[i], G2[par2[i]].pb(i); 312 timer=1; 313 ans=0; 314 dfs1(1); 315 dfs2(1); 316 cout<<ans<<"\n"; 317 } 318 319 int main(){ 320 ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0); 321 //freopen("input.txt", "r", stdin); 322 //freopen("output.txt", "w", stdout); 323 int T; 324 cin>>T; 325 while (T--) Solve(); 326 327 return 0; 328 } 329 ``` 330 331 **better implementation of official solution: AaParsa** 332 333 ``` 334 #include <bits/stdc++.h> 335 using namespace std; 336 337 typedef long long ll; 338 typedef pair<ll, ll> pll; 339 typedef pair<int, int> pii; 340 341 #define X first 342 #define Y second 343 #define endl '\n' 344 345 const int N = 3e5 + 10; 346 347 int t, n, L[N], R[N], timer, now, ans; 348 vector<int> Srsh[N], Msht[N]; 349 set<pii> st; 350 351 void MshtDFS(int u) { 352 L[u] = timer++; 353 for (int v : Msht[u]) { 354 MshtDFS(v); 355 } 356 R[u] = timer; 357 } 358 359 int ispar(int u, int v) { 360 return L[u] <= L[v] && R[v] <= R[u]; 361 } 362 363 void SrshDFS(int u) { 364 int last = now; 365 // add u 366 auto it = st.lower_bound({L[u], 0}); 367 if (it != st.end()) 368 now += 1 - ispar(u, it->Y); 369 if (it != st.begin()) { 370 auto nxt = it--; 371 now += 1 - ispar(it->Y, u); 372 if (nxt != st.end()) 373 now -= 1 - ispar(it->Y, nxt->Y); 374 } 375 st.insert({L[u], u}); 376 ans = max(ans, now); 377 // DFS 378 for (int v : Srsh[u]) { 379 SrshDFS(v); 380 } 381 // remove u 382 st.erase({L[u], u}); 383 now = last; 384 } 385 386 int main() { 387 ios_base::sync_with_stdio(false); cin.tie(nullptr); 388 cin >> t; 389 while (t --> 0) { 390 cin >> n; 391 for (int i = 1; i <= n; i++) { 392 Srsh[i].clear(); 393 Msht[i].clear(); 394 } 395 for (int u = 2; u <= n; u++) { 396 int par; cin >> par; 397 Srsh[par].push_back(u); 398 } 399 for (int u = 2; u <= n; u++) { 400 int par; cin >> par; 401 Msht[par].push_back(u); 402 } 403 timer = 0; 404 MshtDFS(1); 405 ans = now = 0; 406 SrshDFS(1); 407 cout << ans + 1 << endl; 408 } 409 return 0; 410 } 411 ``` 412 413 **python solution: Tet** 414 415 ``` 416 #!/usr/bin/env python 417 import os 418 import sys 419 from io import BytesIO, IOBase 420 421 # region fastio 422 423 BUFSIZE = 8192 424 425 426 class FastIO(IOBase): 427 newlines = 0 428 429 def __init__(self, file): 430 self._fd = file.fileno() 431 self.buffer = BytesIO() 432 self.writable = "x" in file.mode or "r" not in file.mode 433 self.write = self.buffer.write if self.writable else None 434 435 def read(self): 436 while True: 437 b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE)) 438 if not b: 439 break 440 ptr = self.buffer.tell() 441 self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr) 442 self.newlines = 0 443 return self.buffer.read() 444 445 def readline(self): 446 while self.newlines == 0: 447 b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE)) 448 self.newlines = b.count(b"\n") + (not b) 449 ptr = self.buffer.tell() 450 self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr) 451 self.newlines -= 1 452 return self.buffer.readline() 453 454 def flush(self): 455 if self.writable: 456 os.write(self._fd, self.buffer.getvalue()) 457 self.buffer.truncate(0), self.buffer.seek(0) 458 459 460 class IOWrapper(IOBase): 461 def __init__(self, file): 462 self.buffer = FastIO(file) 463 self.flush = self.buffer.flush 464 self.writable = self.buffer.writable 465 self.write = lambda s: self.buffer.write(s.encode("ascii")) 466 self.read = lambda: self.buffer.read().decode("ascii") 467 self.readline = lambda: self.buffer.readline().decode("ascii") 468 469 470 sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout) 471 input = lambda: sys.stdin.readline().rstrip("\r\n") 472 473 class FenwickTree: 474 def __init__(self, x): 475 """transform list into BIT""" 476 self.bit = x 477 for i in range(len(x)): 478 j = i | (i + 1) 479 if j < len(x): 480 x[j] += x[i] 481 def update(self, idx, x): 482 """updates bit[idx] += x""" 483 while idx < len(self.bit): 484 self.bit[idx] += x 485 idx |= idx + 1 486 487 def query(self, end): 488 """calc sum(bit[:end])""" 489 end += 1 490 x = 0 491 while end: 492 x += self.bit[end - 1] 493 end &= end - 1 494 return x 495 496 def findkth(self, k): 497 """Find largest idx such that sum(bit[:idx]) <= k""" 498 idx = -1 499 for d in reversed(range(len(self.bit).bit_length())): 500 right_idx = idx + (1 << d) 501 if right_idx < len(self.bit) and k >= self.bit[right_idx]: 502 idx = right_idx 503 k -= self.bit[idx] 504 return idx + 1 505 506 g1 = [] 507 g2 = [] 508 st = [] 509 ft = [] 510 511 def dfs1(graph, start=0): 512 n = len(graph) 513 tim = 1 514 visited = [False] * n 515 stack = [start] 516 while stack: 517 start = stack[-1] 518 if not visited[start]: 519 st[start] = tim 520 tim = tim + 1 521 visited[start] = True 522 for child in graph[start]: 523 if not visited[child]: 524 stack.append(child) 525 else: 526 stack.pop() 527 ft[start] = tim 528 529 530 531 def Do(v): 532 global ans , cnt , mem 533 fen.update(st[v] , 1); 534 if(fen.query(ft[v] - 1) - fen.query(st[v])): 535 mem += [[v , 0 , 0]] 536 return; 537 u = fen2.query(st[v]); 538 ok[v] = 1 539 cnt += 1 540 fen2.update(st[v] , v - u) 541 fen2.update(ft[v] , u - v) 542 mem += [[v , u , ok[u]]] 543 cnt -= ok[u] 544 ok[u] = 0 545 return; 546 547 548 549 def undo(): 550 global cnt , ans , mem 551 [v , u , a] = mem[-1] 552 if(a != 0): 553 ok[u] = 1 554 cnt += 1 555 cnt -= 1 556 ok[v] = 0 557 fen.update(st[v] , -1) 558 fen2.update(st[v] , u - v) 559 fen2.update(ft[v] , v - u) 560 mem.pop() 561 return; 562 563 564 def dfs(graph, start=0): 565 global ans , cnt 566 n = len(graph) 567 visited = [False] * n 568 stack = [start] 569 while stack: 570 start = stack[-1] 571 if not visited[start]: 572 Do(start) 573 ans = max(ans , cnt) 574 visited[start] = True 575 for child in graph[start]: 576 if not visited[child]: 577 stack.append(child) 578 else: 579 stack.pop() 580 undo() 581 582 583 584 def solve(): 585 global n, g1 , g2 , V , st , ft , fen , fen2 , mem , ok , cnt , ans 586 n = int(input()) 587 if(n == 1): 588 print(1) 589 exit(0) 590 591 g1 = [] ; g2 = [] 592 593 for i in range(n): 594 g1.append([]) 595 g2.append([]) 596 597 # 0 base 598 599 V = list(map(int , input().split())) 600 601 for i in range ( 1 , n ): 602 v = V[i - 1]-1 603 g1[v].append(i) 604 605 V = list(map(int , input().split())) 606 607 for i in range ( 1 , n ): 608 v = V[i-1]-1 609 g2[v].append(i) 610 st = [0] * (n + 100) 611 ft = [0] * (n + 100) 612 fen = FenwickTree([0] * (n + 3)) 613 fen2 = FenwickTree([0] * (n + 3)) 614 mem = [] 615 ok = [0]*(n + 100) 616 cnt = 0 617 ans = 0 618 dfs1(g2) 619 dfs(g1) 620 print(ans) 621 622 q = int(input()) 623 for i in range (q): 624 solve() 625 ``` 626 627 **another O(n.log) solution with seg-tree: N.N_2004** 628 629 ``` 630 #include<bits/stdc++.h> 631 #define lc (id * 2) 632 #define rc (id * 2 + 1) 633 #define md ((s + e) / 2) 634 #define dm ((s + e) / 2 + 1) 635 #define ln (e - s + 1) 636 using namespace std; 637 638 typedef long long ll; 639 const ll MXN = 3e5 + 10; 640 const ll MXS = MXN * 4; 641 ll n, timer, ans, Ans; 642 ll lazy[MXS], seg[MXS]; 643 ll Stm[MXN], Ftm[MXN]; 644 vector<ll> adj[MXN][2]; 645 void Build(ll id = 1, ll s = 1, ll e = n){ 646 lazy[id] = -1, seg[id] = 0; 647 if(ln > 1) Build(lc, s, md), Build(rc, dm, e); 648 } 649 void Shift(ll id, ll s, ll e){ 650 if(lazy[id] == -1) return; 651 seg[id] = lazy[id]; 652 if(ln > 1) lazy[lc] = lazy[rc] = lazy[id]; 653 lazy[id] = -1; 654 } 655 void Upd(ll l, ll r, ll x, ll id = 1, ll s = 1, ll e = n){ 656 Shift(id, s, e); 657 if(e < l || s > r) return; 658 if(l <= s && e <= r){ 659 lazy[id] = x; Shift(id, s, e); 660 return; 661 } 662 Upd(l, r, x, lc, s, md), Upd(l, r, x, rc, dm, e); 663 seg[id] = max(seg[lc], seg[rc]); 664 } 665 ll Get(ll l, ll r, ll id = 1, ll s = 1, ll e = n){ 666 Shift(id, s, e); 667 if(e < l || s > r) return 0; 668 if(l <= s && e <= r) return seg[id]; 669 return max(Get(l, r, lc, s, md), Get(l, r, rc, dm, e)); 670 } 671 void prep(ll u, ll par, ll f){ 672 Stm[u] = ++ timer; 673 for(auto v : adj[u][f]){ 674 if(v != par) prep(v, u, f); 675 } 676 Ftm[u] = timer; 677 } 678 bool Is_Jad(ll j, ll u){ 679 return (Stm[j] <= Stm[u] && Ftm[u] <= Ftm[j]); 680 } 681 void DFS(ll u, ll par, ll f){ 682 ll j = Get(Stm[u], Ftm[u]); 683 if(!j) Upd(Stm[u], Ftm[u], u), ans ++; 684 else{ 685 if(Is_Jad(j, u)){ 686 Upd(Stm[j], Ftm[j], 0); 687 Upd(Stm[u], Ftm[u], u); 688 } 689 } 690 Ans = max(Ans, ans); 691 for(auto v : adj[u][f]){ 692 if(v != par) DFS(v, u, f); 693 } 694 if(!j) Upd(Stm[u], Ftm[u], 0), ans --; 695 else{ 696 if(Is_Jad(j, u)){ 697 Upd(Stm[u], Ftm[u], 0); 698 Upd(Stm[j], Ftm[j], j); 699 } 700 } 701 } 702 void solve(){ 703 cin >> n, timer = ans = Ans = 0; 704 for(int i = 1; i <= n; i ++) adj[i][0].clear(), adj[i][1].clear(); 705 for(int t = 0; t < 2; t ++) for(int u = 2, v; u <= n; u ++){ 706 cin >> v, adj[v][t].push_back(u), adj[u][t].push_back(v); 707 } 708 Build(), prep(1, 0, 1); 709 DFS(1, 0, 0); 710 cout << Ans << '\n'; 711 } 712 int main(){ 713 ios::sync_with_stdio(0);cin.tie(0); cout.tie(0); 714 ll q; cin >> q; 715 while(q --) solve(); 716 return 0; 717 } 718 /*! 719 HE'S AN INSTIGATOR, 720 ENEMY ELIMINATOR, 721 AND WHEN HE KNOCKS YOU BETTER 722 YOU BETTER LET HIM IN. 723 */ 724 //! N.N 725 ``` 726 727 [1528D - It's a bird! No, it's a plane! No, it's AaParsa!](/contest/1528/problem/D "Codeforces Round 722 (Div. 1)") 728 729 problem idea and solution: [AmShZ](/profile/AmShZ "Grandmaster AmShZ"), [AliShahali1382](/profile/AliShahali1382 "International Grandmaster AliShahali1382") 730 731 **editorial** 732 733 Tutorial is loading... 734 735 **official solution** 736 737 ``` 738 #include <bits/stdc++.h> 739 #pragma GCC optimize ("O2,unroll-loops") 740 //#pragma GCC optimize("no-stack-protector,fast-math") 741 742 using namespace std; 743 typedef long long ll; 744 typedef long double ld; 745 typedef pair<int, int> pii; 746 typedef pair<pii, int> piii; 747 typedef pair<ll, ll> pll; 748 #define debug(x) cerr<<#x<<'='<<(x)<<endl; 749 #define debugp(x) cerr<<#x<<"= {"<<(x.first)<<", "<<(x.second)<<"}"<<endl; 750 #define debug2(x, y) cerr<<"{"<<#x<<", "<<#y<<"} = {"<<(x)<<", "<<(y)<<"}"<<endl; 751 #define debugv(v) {cerr<<#v<<" : ";for (auto x:v) cerr<<x<<' ';cerr<<endl;} 752 #define all(x) x.begin(), x.end() 753 #define pb push_back 754 #define kill(x) return cout<<x<<'\n', 0; 755 756 const int inf=1000000010; 757 const ll INF=1000000000000001000LL; 758 const int mod=1000000007; 759 const int N=605; 760 761 int n, m, k, u, v, x, y, t, a, b; 762 bool mark[N]; 763 int G[N][N], D[N]; 764 765 inline void upd(int &x, int y){ if (x>y) x=y;} 766 767 int main(){ 768 ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0); 769 memset(G, 63, sizeof(G)); 770 cin>>n>>m; 771 while (m--){ 772 cin>>u>>v>>x; 773 G[u][v]=min(G[u][v], x); 774 } 775 for (int i=0; i<n; i++){ 776 memset(D, 63, sizeof(D)); 777 memset(mark, 0, sizeof(mark)); 778 for (int v=0; v<n; v++) upd(D[v], G[i][v]); 779 while (1){ 780 int v=-1; 781 for (int x=0; x<n; x++) if (!mark[x]){ 782 if (v==-1 || D[v]>D[x]) v=x; 783 } 784 if (v==-1) break ; 785 mark[v]=1; 786 upd(D[(v+1)%n], D[v]+1); 787 for (int u=0; u<n; u++) 788 upd(D[(u+D[v])%n], D[v]+G[v][u]); 789 790 } 791 for (int j=0; j<n; j++){ 792 if (i==j) cout<<"0 "; 793 else cout<<D[j]<<" "; 794 } 795 cout<<"\n"; 796 } 797 798 return 0; 799 } 800 ``` 801 802 **a different O(n^3) solution: Atreus** 803 804 ``` 805 #include <bits/stdc++.h> 806 807 using namespace std; 808 809 typedef long long ll; 810 811 const int maxn = 600 + 5; 812 813 int n; 814 int dp[maxn]; 815 bool mark[maxn]; 816 vector<pair<int,int>> g[maxn]; 817 int go[maxn]; 818 819 int dis(int s, int t) { 820 if (s <= t) 821 return t - s; 822 return n - (s - t); 823 } 824 825 void dijkstra(int src) { 826 memset(dp, 63, sizeof dp); 827 memset(mark, 0, sizeof mark); 828 dp[src] = 0; 829 set<int> S; 830 for (int i = 0; i < n; i++) 831 S.insert(i); 832 for (int i = 0; i < n - 1; i++) { 833 int v = -1; 834 for (int j = 0; j < n; j++) { 835 if (mark[j]) 836 continue; 837 if (v == -1 or dp[v] > dp[j]) 838 v = j; 839 } 840 S.erase(v); 841 mark[v] = 1; 842 if (v != src) { 843 auto it = S.lower_bound(v); 844 if (it == S.end()) 845 it = S.lower_bound(0); 846 int nex = *it; 847 dp[nex] = min(dp[nex], dp[v] + dis(v, nex)); 848 } 849 for (int i = 2 * n - 1; i >= 0; i--) { 850 int v = i % n; 851 if (!mark[v]) 852 go[v] = v; 853 else 854 go[v] = go[(v + 1) % n]; 855 } 856 for (auto [u, w] : g[v]) { 857 int nex = go[(u + dp[v]) % n]; 858 dp[nex] = min(dp[nex], dp[v] + w + dis((u + dp[v]) % n, nex)); 859 } 860 } 861 } 862 863 int main() { 864 ios_base::sync_with_stdio(false); 865 int m; 866 cin >> n >> m; 867 for (int i = 0; i < m; i++) { 868 int v, u, w; 869 cin >> v >> u >> w; 870 g[v].push_back({u, w}); 871 } 872 for (int i = 0; i < n; i++) { 873 dijkstra(i); 874 for (int j = 0; j < n; j++) 875 cout << dp[j] << " \n"[j == n-1]; 876 } 877 } 878 ``` 879 880 [1528E - Mashtali and Hagh Trees](/contest/1528/problem/E "Codeforces Round 722 (Div. 1)") 881 882 problem idea and solution: [AliShahali1382](/profile/AliShahali1382 "International Grandmaster AliShahali1382") 883 884 Thanks to [Kininarimasu](/profile/Kininarimasu "Master Kininarimasu") for the editorial. 885 886 **editorial** 887 888 Tutorial is loading... 889 890 **official solution** 891 892 ``` 893 #include <bits/stdc++.h> 894 #pragma GCC optimize ("O2,unroll-loops") 895 //#pragma GCC optimize("no-stack-protector,fast-math") 896 897 using namespace std; 898 typedef long long ll; 899 typedef long double ld; 900 typedef pair<int, int> pii; 901 typedef pair<pii, int> piii; 902 typedef pair<ll, ll> pll; 903 #define debug(x) cerr<<#x<<'='<<(x)<<endl; 904 #define debugp(x) cerr<<#x<<"= {"<<(x.first)<<", "<<(x.second)<<"}"<<endl; 905 #define debug2(x, y) cerr<<"{"<<#x<<", "<<#y<<"} = {"<<(x)<<", "<<(y)<<"}"<<endl; 906 #define debugv(v) {cerr<<#v<<" : ";for (auto x:v) cerr<<x<<' ';cerr<<endl;} 907 #define all(x) x.begin(), x.end() 908 #define pb push_back 909 #define kill(x) return cout<<x<<'\n', 0; 910 911 const int inf=1000000010; 912 const ll INF=1000000000000001000LL; 913 const int mod=998244353, inv6=166374059; 914 const int MAXN=1000010, LOG=20; 915 916 ll n, m, k, u, v, x, y, t, a, b, ans; 917 ll dp[MAXN], ps[MAXN]; 918 ll pd[MAXN], sp[MAXN]; 919 920 ll C3(ll x){ 921 return x*(x-1)%mod*(x-2)%mod*inv6%mod; 922 } 923 ll C2(ll x){ 924 return x*(x-1)/2%mod; 925 } 926 927 int main(){ 928 ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0); 929 //freopen("input.txt", "r", stdin); 930 //freopen("output.txt", "w", stdout); 931 cin>>n; 932 dp[0]=ps[0]=1; 933 pd[0]=sp[0]=1; 934 for (int i=1; i<=n; i++){ 935 ps[i]=(1 + ps[i-1] + ps[i-1]*(ps[i-1]+1)/2)%mod; 936 dp[i]=ps[i]-ps[i-1]; 937 pd[i]=dp[i]-dp[i-1]; 938 sp[i]=(sp[i-1]+pd[i])%mod; 939 } 940 for (int i=0; i<n; i++) ans=(ans + pd[i]*sp[n-1-i])%mod; 941 942 ans=(ans + 2*C3(ps[n-1]+2))%mod; 943 if (n>=2) ans=(ans - 2*C3(ps[n-2]+2))%mod; 944 945 ans=(ans + 2*C2(ps[n-1]+1))%mod; 946 if (n>=2) ans=(ans - 2*C2(ps[n-2]+1))%mod; 947 948 if (ans<0) ans+=mod; 949 cout<<ans<<"\n"; 950 951 return 0; 952 } 953 ``` 954 955 [1528F - AmShZ Farm](/contest/1528/problem/F "Codeforces Round 722 (Div. 1)") 956 957 problem idea and solution: [AmShZ](/profile/AmShZ "Grandmaster AmShZ"), [AliShahali1382](/profile/AliShahali1382 "International Grandmaster AliShahali1382") 958 959 **editorial** 960 961 Tutorial is loading... 962 963 **official solution** 964 965 ``` 966 # include <bits/stdc++.h> 967 968 using namespace std; 969 970 typedef long long ll; 971 typedef long double ld; 972 typedef pair <int, int> pii; 973 typedef pair <pii, int> ppi; 974 typedef pair <int, pii> pip; 975 typedef pair <pii, pii> ppp; 976 typedef pair <ll, ll> pll; 977 978 # define A first 979 # define B second 980 # define endl '\n' 981 # define sep ' ' 982 # define all(x) x.begin(), x.end() 983 # define kill(x) return cout << x << endl, 0 984 # define SZ(x) int(x.size()) 985 # define lc id << 1 986 # define rc id << 1 | 1 987 # define InTheNameOfGod ios::sync_with_stdio(0);cin.tie(0); cout.tie(0); 988 989 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));} 990 991 const int xn = 3e5 + 10; 992 const int xm = 18; 993 const int sq = 320; 994 const int inf = 1e9 + 10; 995 const ll INF = 1e18 + 10; 996 const int mod = 998244353; 997 const int base = 257; 998 999 int n, k, C[xn], ans, A[xn], B[xn], rev[xn]; 1000 int fact[xn], ifact[xn]; 1001 1002 void NTT(int *A, bool inv){ 1003 int n = (1 << xm); 1004 for (int i = 0; i < (1 << xm); ++ i) 1005 if (rev[i] < i) 1006 swap(A[i], A[rev[i]]); 1007 for (int ln = 1; ln < n; ln <<= 1){ 1008 int w = power(3, mod / 2 / ln, mod); 1009 if (inv) 1010 w = power(w, mod - 2, mod); 1011 for (int i = 0; i < n; i += ln + ln){ 1012 int wn = 1; 1013 for (int j = i; j < i + ln; ++ j){ 1014 int x = A[j], y = 1ll * A[j + ln] * wn % mod; 1015 A[j] = (x + y) % mod; 1016 A[j + ln] = (x - y + mod) % mod; 1017 wn = 1ll * wn * w % mod; 1018 } 1019 } 1020 } 1021 if (inv){ 1022 int invn = power(1 << xm, mod - 2, mod); 1023 for (int i = 0; i < n; ++ i) 1024 A[i] = 1ll * A[i] * invn % mod; 1025 } 1026 } 1027 1028 int main(){ 1029 InTheNameOfGod; 1030 1031 cin >> n >> k; 1032 C[0] = fact[0] = 1; 1033 for (int i = 1; i < xn; ++ i){ 1034 C[i] = 1ll * C[i - 1] * (n - i + 1) % mod * power(i, mod - 2, mod) % mod; 1035 fact[i] = 1ll * fact[i - 1] * i % mod; 1036 } 1037 ifact[xn - 1] = power(fact[xn - 1], mod - 2, mod); 1038 for (int i = xn - 2; i >= 0; -- i) 1039 ifact[i] = 1ll * ifact[i + 1] * (i + 1) % mod; 1040 for (int i = 1; i < (1 << xm); ++ i) 1041 rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (xm - 1)); 1042 for (int i = 0; i <= k; ++ i){ 1043 A[i] = 1ll * power(i, k, mod) * ifact[i] % mod; 1044 B[i] = ifact[i]; 1045 if (i % 2) 1046 B[i] = (mod - B[i]) % mod; 1047 } 1048 NTT(A, 0), NTT(B, 0); 1049 for (int i = 0; i < xn; ++ i) 1050 A[i] = 1ll * A[i] * B[i] % mod; 1051 NTT(A, 1); 1052 for (int i = 1; i <= k; ++ i) 1053 ans = (ans + 1LL * A[i] * C[i] % mod * power(n + 1, n - i, mod) % mod * fact[i] % mod) % mod; 1054 cout << ans << endl; 1055 1056 return 0; 1057 } 1058 ```